[BOJ 9184번] 신나는 함수 실행

1. 문제

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

다음과 같은 재귀함수 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)를 출력한다.

 

---

2. 문제 풀이 방법

 

문제 풀이 접근법1

주어진 재귀 함수를 파이썬 코드로 다시 정리하면

def recursion(a, b, c):
    
    if a <= 0 or b <= 0 or c <= 0: #a,b, c가 0 이하이면 2를 반환
        return 1
        
    elif a > 20 or b > 20 or c > 20: # a, b, c가 20이상이면 20을 다시 함수에 넣어서 반환
        return recursion(20, 20, 20)
    
    elif a < b and b < c: #a <  b < c 아래를 다시 더한 값을 반환
        return recursion(a, b, c-1) + recursion(a, b-1, c-1) - recursion(a, b-1, c)
    
    else: #그 외
        return recursion(a-1, b, c) + recursion(a-1, b-1, c) + recursion(a-1, b, c-1) - recursion(a-1, b-1, c-1)
        

print(recursion(1, 1, 1))

 

아래와 같이 정리할 수 있다. 

 

재귀 함수를 사용하여서 풀었던 문제를 동적 프로그래밍 방법을 사용해서 풀이하는 것이 목표이다. 

 

위의 문제에서 a, b, c는 -50~ 50 사이의 값을 가지고, 1일 경우에는 항상 1을, 20이상일 경우에는 항상 w(20)을 반환하게 된다. 

따라서 반복되는 부분에 대한 계산은 0 < a, b, c < 20 일 때가 되게 된다. (a, b, c가 0이상 20 이하일 경우 recursion을 다시 호출해서 문제를 풀이하게 됨 *코드 참조) 그러므로 해당 부분을 미리 계산해두면, 즉 a, b, c가 각각 0이상 20이하의 수를 가질 경우를 미리 계산해두면 반복되는 계산을 줄이고 바로 값을 가져올 수 있으므로 효율적인 계산이 가능해질 것이다. 

 

1) 3차원 리스트 dp를 정의한다.

2) 함수 w를 정의한다. 

- 만약 a, b, c < 0이면 1을 반환한다.

- 만약 a,b, c > 20이면 w(20, 20, 20)을 넣은 값을 다시 계산하여 반환한다.

- 만약 0 < a, b, c, < 20이고 해당 값이 3차원 리스트 dp에 있으면 해당 값을 반환한다. 

- 만약 0 < a, b, c, < 20이고, 해당 값이 없다면 

• a  < b and b < c이면 w(a,b,c-1) + w(a,b-1,c-1) - w(a, b-1, c) 값을 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) 값을 dp에 넣고, dp[a][b][c]를 반환한다.  

import sys


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

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 dp[a][b][c]:
        return dp[a][b][c]
    
    elif 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]
    
    else:
        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:
    answer = 0
    abc = list(map(int, sys.stdin.readline().split()))
    
    if abc[0] == -1 and abc[1] == -1 and abc[2] == -1:
        break
    
    answer = w(abc[0], abc[1], abc[2])
    
    print("w({0}, {1}, {2}) = {3}".format(abc[0], abc[1], abc[2], answer))

 

---

 

3. 동적 프로그래밍(DP)

동적 프로그래밍(Dynamic Programming, DP)은 복잡한 문제를 간단한 하위 문제로 분할하여 해결하는 방법입니다. DP는 주로 중복되는 하위 문제를 효율적으로 해결하기 위해 사용되며, 이를 통해 계산 속도를 크게 향상시킬 수 있습니다. DP는 다음 두 가지 핵심 아이디어에 기반합니다:

1. 중복된 계산의 제거(Memoization): 동일한 하위 문제를 여러 번 계산하지 않고, 한 번 계산한 결과를 저장하여 재사용합니다.
2. 최적 부분 구조(Optimal Substructure): 문제의 최적 해답이 그 하위 문제들의 최적 해답으로부터 구성될 수 있습니다.

동적 프로그래밍 문제는 보통 다음과 같은 단계로 해결합니다:

1. 문제 정의

문제를 명확히 정의하고, 문제를 작은 하위 문제들로 분할합니다.

2. 점화식 수립

하위 문제들 간의 관계를 정의하는 점화식을 수립합니다. 점화식은 보통 재귀적인 형태로 표현됩니다.

3. 메모이제이션 또는 테이블 채우기

점화식을 바탕으로 하위 문제의 해를 메모이제이션 기법(탑다운 접근)이나 테이블에 채워가는 방식(바텀업 접근)으로 계산합니다.

4. 최적 해답 도출

테이블이나 메모이제이션 결과를 이용하여 최종 문제의 해답을 도출합니다

---

 

참고:https://yellowtail2357.tistory.com/20

[백준] 9184 신나는 함수 실행 (python 파이썬)