[Python] 백준 9184번 - 신나는 함수 실행(실버2)

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

9184번: 신나는 함수 실행

 

혼자 힘으로 풀었는가? O

알고리즘 분류
 - 다이나믹 프로그래밍
 - 재귀

 

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 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

 

---

 

우선 위 문제를 코드로 구현하면

 

import sys
input = sys.stdin.readline

def w(a, b, c):
    if a <= 0 or b <=0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
    elif a < b < c:
        return w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    else:
        return w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        exit()
    result = w(a, b, c)
    print(f'w({a}, {b}, {c}) = {result}')

위와같이 표현할 수 있다.

 

여기서 예시중 하나인

 

10 4 6을 넣어봣는데

 

5초이상 걸려도 답이 안나오는것을 보고

 

'아 이건 DP로 풀어야하는 구나' 하고 코드를 다시 작성했다.

---

 

from sys import stdin
input = stdin.readline

dp = [[[ 0 for _ in range(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
            elif 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]

while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        exit()
    if a <= 0 or b <=0 or c <= 0:
        print(f'w({a}, {b}, {c}) = 1')
    else:
        if a > 20 or b > 20 or c > 20:
            q, w, e = 20, 20, 20
            print(f'w({a}, {b}, {c}) = {dp[q][w][e]}')
        else:
            print(f'w({a}, {b}, {c}) = {dp[a][b][c]}')

dp테이블을 먼저 작성하는 이유는 어차피 -50~50 사이의 숫자에서 무엇이 나오든 같은 결과를 가지고 뭔지만 출력하면 되기 때문에 DP테이블을 먼저 구성하였고, 이후 값을 뽑아내기만 하면 되게끔 하였다.

 

-50~0까지는 고려대상이 아니기 때문에 1만 출력하면 되고

21~50까지는 어차피 20으로 초기화시켜서 진행하기 때문에 배열을 0~21까지만 만들어주면 되었다.

 

이후 적힌 공식대로 그대로 DP테이블을 만들어서 값만 뽑아내주면 끝이다.

 

---

3% 에서 틀렸습니다 나오는 사람들!!

 

1 출력하는곳에서 'w(a, b, c) = 1' 해줫는지 확인할 것