[Baekjoon] 9184번 신나는 함수 실행 문제 리뷰

이번엔 백준에서 제공하는 기본적인 동적 프로그래밍 문제인 9184번 신나는 함수 실행 문제에 대해서 리뷰해 보도록 하겠습니다.

문제 소개

다음과 같은 재귀함수 w(a, b, c)가 있다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면 a=15, b=15, c=15)
a, b, c 가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서 w(a, b, c)를 출력한다.

제한

$-50<=a,b,c<=50$

예제 입력

1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1

예제 출력

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1047576
w(-1, 7, 18) = 1

문제 풀이

이 문제는 실행에 오래 걸리는 재귀 함수를 동적 프로그래밍으로 바꾸는 문제입니다. 그래서 재귀 함수는 동적 프로그래밍으로 구현이 가능하다는 개념을 알고 계시다면 개념적으로는 접근이 매우 쉬운 문제입니다. 다만 단순히 동적 프로그래밍이라고만 접근하기 보단 문제에서 제시한 재귀 함수를 꼼꼼히 보셔야 합니다. 왜냐하면 함수에 여러가지 함정들이 있어 이 함정들을 캐치하지 못하면 틀릴 수도 있기 때문입니다. 그럼 함수에 있는 각 조건문들이 어떤 의미를 지니고 있는지에 대해서 한 번 살펴보도록 하겠습니다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

첫 번째 조건문은 a, b, c 중에 하나라도 0보다 작거나 같은 것이 있으면 무조건 1을 반환하라는 조건문입니다. 이 조건문을 봤을 때에는 뭐지 했습니다만 이 조건문이 의미하는 바는 바로 동적 프로그래밍을 설계 할 때 필수적인 초기값을 의미합니다. 즉 dp 테이블에서 0번째에 해당하는 값들은 모두 1로 초기화를 해주어야 한다는 의미를 내포하고 있습니다. 또한 가장 먼저 실행 되는 조건문이기 때문에 출력 시 이 조건문에 대한 출력값을 출력해 주어야 합니다.

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

두 번째 조건문은 a, b, c 중에서 하나라도 20보다 큰 값이 있으면 무조건 w(20, 20, 20) 의 값을 반환하도록 하는 조건문입니다. 이 조건문은 제 생각엔 dp 테이블의 제한을 두도록 하는 조건문으로 보입니다. 즉 dp 테이블의 크기는 21x21x21 를 초과할 수 없다는 의미를 간접적으로 내포하고 있는게 아닌가 합니다. 즉 제한으로 둔 $-50<=a,b,c<=50$ 은 일종의 함정이라 dp 테이블의 크기를 100x100x100 으로 해두면 메모리 초과가 뜰 수 있다는 힌트라고 생각했습니다. 또한 출력 시에 첫 번째 조건문 다음으로 출력에 영향을 미치는 조건문이기 때문에 출력값 출력 시에 해당 조건문에 의해서 출력되도록 해야 합니다.

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

마지막 조건문과 else 는 dp 계산에 대한 조건문 입니다. 따라서 dp 테이블에 계산 시 저 조건문 그대로 계산해서 값을 넣도록 하면 되겠습니다. 그럼 코드를 통해 알아보도록 하겠습니다.

"""
baekjoon 9184
"""
import sys

# 동적 프로그래밍으로 계산하는 함수
def run(dp):
    for i in range(1, 21):
        for j in range(1, 21):
            for k in range(1, 21):

                if i < j and j < k: # 첫 번재 인자가 두 번째 인자 보다 작고, 두 번째 인자가 세 번째 인자보다 작을 때 아래 계산을 수행
                    dp[i][j][k] = dp[i][j][k-1] + dp[i][j-1][k-1] - dp[i][j-1][k]
                else: # 그 외의 케이스는 아래 계산을 수행
                    dp[i][j][k] = dp[i-1][j][k] + dp[i-1][j-1][k] + dp[i-1][j][k-1] - dp[i-1][j-1][k-1]


# 값을 저장할 3차원 리스트로 dp 리스트 생성
dp = [[[0 for col in range(21)] for row in range(21)] for depth in range(21)]

# dp 리스트에서 0이 들어간 원소들은 모두 1의 값을 가지므로 0이 있는 모든 곳에는 1로 업데이트 즉 초기값 업데이트
for i in range(0, 21):
    for j in range(0, 21):
        for k in range(0, 21):
            if i == 0 or j == 0 or k == 0:
                dp[i][j][k] = 1

dp[1][1][1] = 0

# 함수 실행
run(dp)

# 입력을 받아올 리스트
input_list = []

# 입력을 받아옴
while True:
    input = sys.stdin.readline

    a, b, c = map(int, input().split())

    # a, b, c 값이 모두 -1 이면 조건문 종료
    if a == -1 and b == -1 and c == -1:
        break

    # input_list 에 세 가지 값을 튜플로 하여 저장
    input_list.append((a, b, c))

for i in input_list:
    a, b, c = i[0], i[1], i[2]

    # a, b, c 세 가지 값 중 하나라도 0이면 1을 출력하도록 함
    if a <= 0 or b <= 0 or c <= 0:
        print("w(%d, %d, %d) = %d" % (i[0], i[1], i[2], 1))
        continue

    # a, b, c 값 중 하나라도 20보다 크면 dp[20][20][20] 을 출력하도록 함
    if a > 20 or b > 20 or c > 20:
        print("w(%d, %d, %d) = %d" % ( i[0], i[1], i[2], dp[20][20][20]))
        continue

    # 위 두 조건에 해당하지 않으면 그대로 출력
    print("w(%d, %d, %d) = %d" % (i[0], i[1], i[2], dp[a][b][c]))

1. 저는 dp 테이블을 리스트로 구성을 했고, 3차원 리스트로 구성하고 구성 요소의 모든 값은 0으로 초기화 해주었습니다.

2. 그리고 문제에 따라 dp 테이블에서 인덱스 값에 0이 들어가는 곳은 모두 1로 초기화 해주었습니다.

3. 21x21x21 은 9261 정도 되기 때문에 이 문제의 경우 모든 케이스에 대해서 미리 계산을 해두도록 해도 시간 초과가 나지 않겠다고 생각을 해서 초기값을 모두 지정해 두고, dp 테이블로 모든 값을 미리 계산하도록 하였습니다.

4. 주어진 입력을 받도록 하고, 입력 값에서 첫 번째와 두 번째 조건문에 해당하는지 검사하고 해당하면 그에 맞게 출력하도록 조정하였고, 그게 아니라면 dp 테이블에서 입력 값에 맞는 인덱스의 값을 받아오도록 하였습니다.

문제 풀이 후기

이 문제는 전형적인 동적 프로그래밍 문제로 동적 프로그래밍의 개념을 알고 있다면 쉽게 풀 수 있는 문제라고 생각합니다. 왜냐하면 동적 프로그래밍에 약한 제가 풀었기 때문이죠 하지만 너무 동적 프로그래밍이다만 생각하고 접근하면 오답이 나고 왜 오답이 나는지 파악하기가 어렵습니다. 그래서 주어진 함수의 조건문을 꼼꼼히 봐야 하며 해당 조건문들이 어떤 의미를 지니는지 파악하는게 이 문제를 맞추기 위해서 중요하다고 저는 생각합니다.

마치며

긴 글 읽어주셔서 감사드리며, 포스트에 잘못된 내용이나 오타 혹은 궁금하신 것이 있으시다면 댓글 달아주시기 바랍니다!