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

import sys
input = sys.stdin.readline

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

dp = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]

while True:
    a, b, c = map(int,input().split())
    
    if a == -1 and b == -1 and c == -1:
        break

    result = w(a,b,c)

    print(f'w({a}, {b}, {c}) = {result}')

이번 문제는 주어진 함수를 구현하여 주어진 입력(a, b, c)의 결과를 출력하는 문제이다.

 

주어진 함수를 그대로 구현하여 실행시키게 되면 경우의 수가 많은 경우에는 시간초과를 받게 되기 때문에, 함수의 결과를 별도의 DP리스트에 저장하여 반복 연산을 줄이는 DP 알고리즘을 사용해서 풀어야 한다.

 

처음에는 테스트 케이스 (10, 4, 6)에서 엉뚱한 값이 나와서 당황했었는데, 이것은 3차원 배열을 초기화하는 방법이 잘못되어서 였다.

 

두번째는 분명 DP 알고리즘을 사용하는 로직은 다른 답들과 동일한데, 코드의 순서가 잘못되어 시간초과를 받았다.(DP리스트에 있는지 확인하기 전에 먼저 가장 작은 문제인지 확인)

 

그리고 입력 값의 범위가 20을 넘어가면 w(20, 20, 20)으로 제한되기 때문에 굳이 DP 리스트의 범위를 51이나 102로 지정해줄 필요 없이 21로만 지정해줘도 충분했다.

 

이번 문제를 통해 배우게 된 점은 다음과 같다.

1. 특정 크기의 2차원(3차원) 리스트를 초기화할 때는 반드시 리스트 컴프리헨션을 사용해야 하는데, 만약에 단순히 곱셈을 사용하여 리스트를 초기화하게 되면 이는 얕은 복사 방식을 사용하게 되어 내부적으로 포함된 리스트가 모두 동일한 객체에 대한 Reference(참조)로 인식되기 때문에 의도치 않은 결과가 나올 수 있다 🚨

 

2. DP를 구현할 때, 다음과 같은 순서로 구현하여야 한다.

• 가장 작은 문제(Sub Problem)에 대한 정답이나 특정 값에 대한 재귀를 먼저 확인하고 return 한다. ex) 피보나치의 n == 1, n == 2
• DP리스트에 값이 존재하는지 확인하여 존재한다면 return 한다.
• DP리스트에 값이 존재하지 않는다면 DP리스트에 값을 저장하고 return 한다.

 

3. DP 리스트에 저장되어야 할 데이터의 범위를 고려하자.

 

아직 DP 문제에 대한 감이 잘 잡히지 않아 실수를 자주 했지만, 앞으로 더 풀어보면서 감을 익혀보기로 했다 :)