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

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

문제

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

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

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, 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 1

2 2 2

10 4 6

50 50 50

-1 7 18

-1 -1 -1

예제 출력 1 

w(1, 1, 1) = 2

w(2, 2, 2) = 4

w(10, 4, 6) = 523

w(50, 50, 50) = 1048576

w(-1, 7, 18) = 1

 

 

---

풀이

a / b / c 의 값이 음수거나 20이상 일때는 재귀호출로 처리하고

그 밑의 논리를 dp형식으로 구현하면된다.

이미 점화식까지 친절하게 다 나와있으므로 전혀 어려울게 없는 문제.

def solution(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:
        return solution(20, 20, 20)

    if dp[a][b][c]:
        return dp[a][b][c]
    if a<b<c :
        dp[a][b][c] = solution(a,b,c-1) + solution(a,b-1,c-1) - solution(a,b-1,c)
        return dp[a][b][c]
    dp[a][b][c] = solution(a-1,b,c) + solution(a-1,b-1,c) + solution(a-1,b,c-1) - solution(a-1,b-1,c-1)
    return dp[a][b][c]
    

while True:
    a, b, c = map(int, input().split())
    dp = [[[0]*21 for _ in range(21)] for __ in range(21)]
    if a == -1 and b == -1 and c == -1:
        break
    print("w(%d, %d, %d) = %d"%(a, b, c, solution(a, b, c)))

• dp가 왜 21 by 21 인가?
  • 어차피 20 이상의 수는 return solution(20, 20, 20)이라는 재귀함수에 의해서 모두 걸러지기 때문이다.