[백준 파이썬] # 9184 신나는 함수 실행

Silver II

# 9184 신나는 함수 실행

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

9184번: 신나는 함수 실행

 

풀이

d = [[[0]*21 for i in range(21)] for j 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:
        return w(20,20,20)

    # 배열에 값이 저장되어 있으면 계산하지 않고 출력
    if d[a][b][c]:
        return d[a][b][c]

    if a<b and b<c:
        # 배열에 값을 저장하고 그 값을 출력
        d[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
        return d[a][b][c]
    else:
        d[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[a][b][c]

while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break
    print('w({0}, {1}, {2}) = {3}'.format(a,b,c,w(a,b,c)))

 

후기

• DP 문제 (1. 최적 부분 구조, 2. 중복되는 부분 문제) 해당
• 메모이제이션을 활용해야 하는 문제

이전에 문제를 풀었던 스터디원의 도움을 받았다

• '[[[0]21] * 21] * 21' != '[[[0]21 for j in range(21)] for i in range(21)] 과 다르다!!'
• 신나는 함수실행이라니.. 제목 지은 사람 꿀밤이라도 멕이고 싶다..