BAEKJOON-9184 : 신나는 함수 실행

BEAKJOON-9184 : 신나는 함수 실행

동적 프로그래밍을 이용하면 쉽게 풀 수 있다.

이 문제 설명을 보고 이 문제를 어떻게 동적 프로그래밍 기법을 이용하여 풀까 고민했지만,

문제 조건과 재귀 호출이 어떻게 이루어지는지 보고 금방 알 수 있었다.

코드

arr = [[[1 for _ in range(21)] for _ in range(21)] for _ in range(21)]

for i in range(1,21):
    for j in range(1,21):
        for k in range(1,21):
            if i < j and j < k:
                arr[i][j][k] = arr[i][j][k-1] + arr[i][j-1][k-1] - arr[i][j-1][k]
            else:
                arr[i][j][k] = arr[i-1][j][k] + arr[i-1][j-1][k] + arr[i-1][j][k-1] - arr[i-1][j-1][k-1]

a, b, c = map(int, input().split())
while not (a == -1 and b == -1 and c == -1):
    print("w("+str(a)+", "+str(b)+", "+str(c)+") =", end=' ')
    if a <= 0 or b <= 0 or c <= 0:
        print(1)
    elif a > 20 or b > 20 or c > 20:
        print(arr[20][20][20])
    else:
        print(arr[a][b][c])
    a, b, c = map(int, input().split())

조건을 보면 알 수 있듯이 입력되는 수 중에서 0보다 작은 수는 결국 0으로 바뀌어야 하고, 20보다 큰 수는 모든 입력을 20으로 바꿔야 한다.

그래서 동적 프로그래밍에 쓰일 3중 리스트를 21크기로 생성하여 값을 1로 선언해준다.

숫자 3 개를 a, b, c라고 할 때, a, b, c 중에 하나라도 0이 되면 1을 반환해야하므로

a, b, c가 0일 때는 계산을 하지 않고,

1 이상일 때부터 20때까지 3중 반복문을 돌려 문제에서 제시된 계산을 해준다.

이것을 모두 수행하면 입력이 들어올 때마다 계산을 하지 않아도 답을 얻을 수 있다.