미소를뿌리는감자의 코딩
[백준 2024/03/19] 9184번 신나는 함수 실행 본문
728x90
https://www.acmicpc.net/problem/9184
1. 접근 방법
처음에 고민을 하다가, w(1, 1, 1)의 값은 동일할 것이고, 코드를 실행하면서 해당 값의 필요성이 중복될 것이라 생각이 들었다.
따라서 memoization을 사용해야겠다고 생각이 들었다.
dict_r = {} 라는 dictionary를 만들고,
만약 특정 값이 dictionary에 저장되어 있으면, 바로 해당 값을 return 해주었으며
없다면, 그 값을 구하고 딕셔너리에 없는 값이 구해졌을 땐, dictionary에 해당 값을 추가해주었다.
2. 코드
x, y, z = map(int, input().split())
dict_r = {}
def f(a, b, c):
if (a, b, c) in dict_r:
return dict_r[(a, b, c)]
elif a <= 0 or b <= 0 or c <= 0:
dict_r[(a, b, c)] = 1
elif a > 20 or b > 20 or c > 20:
dict_r[(a, b, c)] = f(20, 20, 20)
elif a < b < c:
dict_r[(a, b, c)] = f(a, b, c - 1) + f(a, b - 1, c - 1) - f(a, b - 1, c)
else:
dict_r[(a, b, c)] = f(a - 1, b, c) + f(a - 1, b - 1, c) + f(a - 1, b, c - 1) - f(a - 1, b - 1, c - 1)
return dict_r[(a, b, c)]
while x != -1 or y != -1 or z != -1:
print("w({a}, {b}, {c}) = {d}".format(a=x, b=y, c=z, d=f(x, y, z)))
x, y, z = map(int, input().split())
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/03/21] 1932번 정수 삼각형 (0) | 2024.03.21 |
---|---|
[백준 2024/03/20] 9461번 파도반 수열 (0) | 2024.03.20 |
[백준 2024/02/28] 1149번 RGB거리 (0) | 2024.02.28 |
[백준 2024/02/28] 5705번 Hexagonal Tiles (1) | 2024.02.28 |
[백준 2024/02/27] 2579번 계단 오르기 (0) | 2024.02.27 |