반응형
9184번: 신나는 함수 실행
입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.
www.acmicpc.net
코드
MAX_NUM = 51
dp = [[[0 for i in range(MAX_NUM)] for i in range(MAX_NUM)] for i in range(MAX_NUM)]
def w(a, b, c):
if a <= 0 or b <= 0 or c <= 0:
return 1
if dp[a][b][c]:
return dp[a][b][c]
if a > 20 or b > 20 or c > 20:
return w(20,20,20)
elif a < b and b < c:
dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
return dp[a][b][c]
else:
dp[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 dp[a][b][c]
while True:
x, y, z = map(int, input().split())
if x == -1 and y == -1 and z == -1:
break
print("w(%d, %d, %d) = %d" %(x, y, z, w(x, y, z)))
문제에서 알려준 함수대로 구현을 먼저하되,
메모이제이션을 이용해서 이미 구한 적 있는 값은 다음 과정을 거치지 않고 바로 반환할 수 있도록 한다.
새로 알게된 문법 )
3차원 리스트 초기화하기 !
MAX_NUM = 51
dp = [[[0 for i in range(MAX_NUM)] for i in range(MAX_NUM)] for i in range(MAX_NUM)]
MAX_NUM을 5로 한다면,
이렇게 된다고 생각하면 된다.
반응형
'Programming > Coding Test' 카테고리의 다른 글
| [알고리즘 정리] 동적계획법 (DP) (0) | 2021.05.08 |
|---|---|
| [알고리즘 정리] DFS / BFS (0) | 2021.05.03 |
| 백준 4949 - deque를 이용해서 스택 문제풀기 (0) | 2021.01.12 |
| 백준 5430 - 줄바꿈없이 print, split(), indexing, replace(), join (0) | 2021.01.12 |
| 백준 1021 - deque를 이용해서 풀어보았습니다 (0) | 2021.01.12 |