[동적 계획법 1] [Python] 9184번. 신나는 함수 실행

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

 

 

 

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

---

해결 방법

dp를 활용한다.

 

 

해결 과정

[0][0][0] ~ [20][20][20]의 3차원 배열을 생성하고 각 조건별로 나눈다. 

특정 범위 이내에 들어오면 dp를 계산한다.

특정 위치의 dp의 값이 0이 아닌 경우 이미 계산되어 있는 dp이므로 별도의 계산 과정 없이 바로 출력한다.

 

최종 코드는

 

def w(dp, a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:
        return w(dp, 20, 20, 20)
    
    if dp[a][b][c] != 0:
        return dp[a][b][c]
        
    if a < b and b < c:
        dp[a][b][c] = w(dp, a, b, c-1) + w(dp, a, b-1, c-1) - w(dp, a, b-1, c)
    else:
        dp[a][b][c] = w(dp, a-1, b, c) + w(dp, a-1, b-1, c) + w(dp, a-1, b, c-1) - w(dp, a-1, b-1, c-1)
    
    return dp[a][b][c]
    
def main():
    a, b, c = map(int, input().split())
    dp = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]
    
    while 1:
        if a == -1 and b == -1 and c == -1:
            break
        print("w(%d, %d, %d) = %d" %(a, b, c, w(dp, a, b, c)))
        a, b, c = map(int, input().split())
        
if __name__ == "__main__":
    main()