백준 9184번 python 풀이

9184번은 DP 문제이다.

 

a, b, c 셋 중 하나라도 0 이하이거나 21 이상일 경우 1 또는 w(20,20,20) 값을 반환 해주는 함수이다.

 

문제에 주어진 코드의 경우 재귀적인 방법을 사용 할 때 한 번 했던 계산을 다시하게 된다. 이때 동적 프로그래밍(dynamic programming)을 통해서 불필요한 연산을 건너뛸 수 있다.

 

dp table을 리스트로 생성하고 a, b, c 인데스에 맞게 결과 값을 할당시키면 같은 연산을 다시 할 때 리스트에서 값을 받아오도록 하기만 하면 된다.

 

끝. 

li1 = [[[False for i in range(20)] for i in range(20)] for i in range(20)]
def w(a,b,c,d):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:
        if not d[19][19][19]:
            d[19][19][19] = w(20, 20, 20,d)
        return d[19][19][19]
    elif a < b and b < c :
        if not d[a-1][b-1][c-1]: d[a-1][b-1][c-1] = w(a, b, c-1,d) + w(a, b-1, c-1,d) - w(a,b-1,c,d)
        return d[a-1][b-1][c-1]
    else : 
        if not d[a-1][b-1][c-1]: d[a-1][b-1][c-1] = w(a-1,b,c,d) + w(a-1,b-1,c,d) + w(a-1,b,c-1,d) - w(a-1,b-1,c-1,d)
        return d[a-1][b-1][c-1]
while True:
    x,y,z = map(int,input().split())
    if x==-1 and y==-1 and z==-1:
        break
    print(f"w({x}, {y}, {z}) = {w(x,y,z,li1)}")