9184

날짜 : 2022. 10. 29

사용 언어 : python

 

문제

 

 

코드

import sys

def 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 dp[a][b][c]: 
        return dp[a][b][c] # 값이 이미 존재하면 리턴
    if a < 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]
    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]


dp = [[[0] * 21 for i in range(21)] for j in range(21)]
while True:
    a, b, c = map(int, sys.stdin.readline().split())
    if a == -1 and b == -1 and c == -1:
        break
    print("w(%d, %d, %d) = %d"%(a, b, c, w(a, b, c)))

 

 

알게된 점

- DP에 관해서 애매하게 알고 있었던 것을 확인하는 문제였다.

- 피보나치 문제를 경험으로 단순 for문을 돌려서 문제를 푸는 것이 DP라고 생각했는데 찾아보니 문제를 분할하여 이를 이용해 풀이하는 것이 DP라는 것을 알게되었다.

- 풀이를 보니 중간에 if문을 하나 더 넣음으로써 기존에 값이 이미 존재하는 경우 이를 곧바로 리턴하여 불필요한 재귀를 방지하는 것이 골자였다.

- 그리디는 많이 풀어보았지만 다른 문제들을 풀어보지 않아서 많이 공부해야한다는 것을 알게 되는 문제였다.

 

 

참고 사이트

- https://galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?

- https://seraup.dev/8

백준 9184번 신나는 함수 실행 (Python)

https://namu.wiki/w/메모이제이션

메모이제이션 - 나무위키