[CodingTest] 백준 #9184 신나는 함수 실행

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

이 문제는 동적 계획법 문제이다.

 

내 풀이

import sys
d_abc = [[[0]*21 for i in range(21)] for i in range(21)] 

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:
        if d_abc[20][20][20] ==0:
            d_abc[20][20][20] = w(20,20,20)
        return d_abc[20][20][20] 
    
    
    
    if a < b and b < c:
        if d_abc[a][b][c] ==0:        
            d_abc[a][b][c] = w(a,b,c-1)+w(a,b-1,c-1)-w(a, b-1, c)
        return d_abc[a][b][c]
        

    else:
        if d_abc[a][b][c] ==0:
            d_abc[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 d_abc[a][b][c]

while True:
    a,b,c = map(int,sys.stdin.readline().split())
    if a==-1 and b==-1 and c== -1:
        break
    else:
        print("w({}, {}, {}) = {}".format(a,b,c,w(a,b,c)))

 

처음에 d_abc 배열을 [[[0]*21]*21]*21 로 설정해서 값이 다르게 나와서 애먹었다 ㅠ 

아무리 생각해도 코드에는 이상이 없는 것 같아서 배열을 위와 같이 설정하니 잘 나왔다.

또 input()으로 처음에 받아줬더니 1000ms가 넘게 걸렸는데 readline()으로 바꿔주니 100ms가 나왔다.

다른 사람 풀이도 비슷한 것 같다.