[백준/Python] 9184번: 신나는 함수 실행

문제

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

9184번: 신나는 함수 실행

---

문제 요약

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)

 

위와 같은 재귀함수 w(a, b, c)의 시간 초과 문제를 해결하여

 

a, b, c가 주어졌을 때 w(a, b, c) 값을 형식에 맞게 출력한다.

 

+ 입력의 마지막은 -1, -1, -1이다.

---

코드

def w(a, b, c):
    # a, b, c의 범위가 0 ~ 19를 벗어날 경우 아래 두 조건문에서 처리 (1번의 재귀로 해결)
    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)
    
    # dp[a][b][c]에 w(a, b, c)값이 이전에 이미 계산되어 존재한다면 dp[a][b][c]를 바로 반환
    if dp[a][b][c]:
        return dp[a][b][c]
    
    # dp[a][b][c]가 비어있다면 w(a, b, c)값을 직접 계산하여 저장
    if 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)
    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)
    
    # 위 식에서 계산하여 저장한 dp[a][b][c]를 반환 
    return dp[a][b][c]
    

dp = [[[0] * (21) for _ in range(21)] for _ in range(21)]
# dp[a][b][c]에 w(a. b. c) 저장 -> 다시 구하지 x

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

    if a == -1 and b == -1 and c == -1:
        break
    
    print(f"w({a}, {b}, {c}) = {w(a, b, c)}")

---

코드 설명

1. dp[a][b][c]에 w(a, b, c)를 저장할 메모이제이션 테이블 dp를 생성한다.

+ 같은 값을 여러번 재귀를 통해 구하지 않게 하기 위한 저장 배열이다.

 

2. 문제에 주어진 w(a, b, c)를 구현한다.

 

2 - 1. a, b, c 중 0 이하의 값이 존재하면 1을 반환하고, 21 이상의 값이 존재하면 w(20, 20, 20)을 반환한다.

+ w(20, 20, 20)은 재귀를 통해 계산된다.

 

2 - 2. w(a, b, c)가 이전에 계산되어 이미 dp[a][b][c]에 저장있다면 w(a, b, c)를 다시 계산할 필요 없이 dp[a][b][c]를 반환한다.

 

2 - 3. w(a, b, c)가 dp에 저장되어 있지 않다면 재귀를 통해 w(a, b, c)값을 직접 구하고 dp[a][b][c]에 저장 후, 반환한다.

 

3. w(a, b, c)값을 형식에 맞게 출력한다.