728x90
반응형
※ 문제링크
※ 관련개념
해당 문제는 메모이제이션을 사용하여 풀어야하는 문제였다. 개념만 알면 비교적 간단하게 풀수 있는 문제였다. 메모이제이션은 간단하게 재귀함수를 처음쓸때 호출했던 값들을 모두 딕셔너리에 저장한 후, 특정 값을 구하는 문제가 들어오면 딕셔너리를 참조하여 값이 있는지 확인한 후 있으면 딕셔너리에 저장된 값을, 없으면 재귀함수를 돌려서 푸는 방식이라고 이해하면 되겠다. 자세한 문제풀이 방법과 코드는 아래와 같다.
1. 문제에서 준 함수를 작성하고 함수에서 특정 값들이 들어왔을 때 저장할 딕셔너리 생성
2. 문제에서 주어진 종료조건을 만족할 때까지 반복해서 출력한 반복문 작성
w_dic = {}
def w(a, b, c):
if f'w({a}, {b}, {c})' in w_dic:
return w_dic[f'w({a}, {b}, {c})']
if a <= 0 or b <= 0 or c <= 0:
return 1
if a > 20 or b > 20 or c > 20:
return w(20, 20, 20)
if a < b and b < c:
w_dic[f'w({a}, {b}, {c})'] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
return w_dic[f'w({a}, {b}, {c})']
else:
w_dic[f'w({a}, {b}, {c})'] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
return w_dic[f'w({a}, {b}, {c})']
while True:
a, b, c = map(int, input().split())
if a == -1 and b == -1 and c == -1:
break
print(f'w({a}, {b}, {c}) = {w(a, b, c)}')
P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 9461번 파도반 수열 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
---|---|
[BOJ] 1904번 타일 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
[BOJ] 1003번 피보나치 함수 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
[BOJ] 2004번 조합 0의 개수 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
[BOJ] 1676번 팩토리얼 0의 개수 / 사용언어 : 파이썬(python) (0) | 2021.12.22 |
댓글