[백준] 9184 : 신나는 함수 실행 (Python)

 

출처 : https://www.acmicpc.net/problem/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인 경우는 입력의 마지막을 제외하면 없다. (-50<=a,b,c<=50)

출력

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

 

---

 

아이디어

이번 문제는 재귀 함수에 대한 의사코드를 바탕으로, 시간을 줄인 프로그램을 구현하도록 제시하고 있다. 이러한 유형은 피보나치와 같은 대표적인 중복 연산에 관해 요구사항을 묻는다고 해석할 수 있다. 이에 따라 다음과 같이 알고리즘을 설계할 수 있다.

• BFS + Memozation
• DFS + Memozation
• Loop

BFS + Memozation

방문 처리 배열인 visited(=memo)를 만들어, 중복 연산을 처리할 수 있다. 이 방식으로도 가능하나, 재귀 및 중복 연산과 연관되는 Dynamic Programming인 일명 DP로 필자는 접근하여 프로그램을 구현하였다.

 

Dynamic Programming

다이내믹 프로그래밍은 중복 연산을 줄이기 위해 메모리 공간을 최대 효율로 사용하는 기술이라고 할 수 있다. 일명 DP는 다음과 같은 조건에 부합될 시, 사용 가능하다.

1. 큰 문제를 작은 문제로 쪼갤 수 있다.
2. 작은 문제의 값을 큰 문제의 일부분으로 사용할 수 있다.

피보나치 수열의 경우를 통해, DP의 조건 2가지를 살펴보자. Fibo(6)을 그래프로 시각화해보자.

피보나치 6을 구하는 과정

빨간색 및 파란색 노드를 바탕으로, 3과 4가 중복 연산되는 모습을 확인할 수 있다. 이를 통해, 전역 배열에 미리 3과 4의 연산 값을 한번만 저장해놓으면, 재호출되는 노드에 대한 중복 연산을 줄일 수 있다. 이러한 개념을 메모제이션(Memozation) 기법이라 부른다.

 

DP는 크게 2가지로 다음과 같이 2가지로 구현할 수 있다.

• Top-Down == 하향식
• Bottom-Up == 상향식

탑다운(하향식)은 큰 문제에서 작은 문제로 접근하는 방식이다. 그 과정에서 작은 문제들의 결과값을 저장시켜놨다가, 큰 문제에서 활용하는 것이다. 그렇기 때문에, 탑다운 방식은 재귀함수(DFS)와 메모제이션기법이 활용된다.

반면, 보텀업(상향식)은 작은 문제부터 결과값을 차근차근 저장해서, 큰 문제를 해결할때, 저장한 값을 이용하는 방식이다. For문과 메모제이션 배열인 DP테이블을 활용한다.

 

이를 바탕으로, 현 문제에 대해 상향식과 하향식으로 구현하는 방식을 살펴보자.

 

정답 코드

DFS + Memozation

• DP테이블 : 작은 문제들의 값 저장 (딕셔너리)
• 재귀함수를 통해, 큰 문제에서 작은 문제의 값을 일부 이용한다.

input=__import__('sys').stdin.readline
import sys
sys.setrecursionlimit(10**8)

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 (a,b,c) in dp.keys():
        return dp[(a,b,c)] # 큰 문제에서 작은 문제의 값 활용.
    if a<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)]
    
while True:
    a,b,c=map(int,input().split())
    if (a,b,c)==(-1,-1,-1):
        break
    dp={}
    print(f"w({a}, {b}, {c}) = {w(a,b,c)}")

Loop

• a,b,c 중 한가지라도 음수 또는 0이면, 답은 1이다.
• 즉, 음수 또는 0, 21이상의 수들은 전부 1 또는 dp[20][20][20]으로 치환된다.
• 그러므로, DP테이블은 양수 0~20까지만 작은 문제들의 값을 차근차근 저장시킬 수 있다.
• 이 때, a,b,c 중 하나가 0인 양수 0~20애들은 1이므로, 이들만 초기값 1로 설정한다.

# Bottom-Up 하향식
input=__import__('sys').stdin.readline

while True:
    a,b,c=map(int,input().split())
    if (a,b,c)==(-1,-1,-1):
        break
    
    dp=[[[0]*21 for _ in range(21)] for _ in range(21)]

    # 초기 조건 채우기
    for i in range(21):
        for j in range(21):
            for k in range(21):
                if i==0 or j==0 or k==0:
                    dp[i][j][k]=1
    
    # 1~20까지 DP테이블 채우기
    for i in range(1,21):
        for j in range(1,21):
            for k in range(1,21):
                if i<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]
    
    # 답 출력
    answer=0
    if a<=0 or b<=0 or c<=0:
        answer=1
    elif a>20 or b>20 or c>20:
        answer=dp[20][20][20]
    else:
        answer=dp[a][b][c]
    print(f"w({a}, {b}, {c}) = {answer}")

Bottom-Up 결과

Top-Down 결과

결과를 보면 알 수 있듯이, 보텀업의 결과가 탑다운보다 빠른 시간임을 확인할 수 있다. 탑다운은 재귀이므로, 오버헤드의 영향이 있기 떄문이다. 그러므로, DP로 접근시 보텀업을 지향하는 것이 좋다.