Yunsu's Log

BOJ 9184: 신나는 함수 실행

7 min read

Note

메모이제이션을 활용하여 재귀 함수를 최적화하는 문제입니다.

문제

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

다음과 같은 재귀함수 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)를 출력하는 프로그램을 작성하시오.

문제 링크: https://www.acmicpc.net/problem/9184

입력

입력은 세 정수 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) 조합이 여러 번 계산됨
  • 최적화 필요: 메모이제이션을 사용하여 중복 계산 제거

왜 느린가?

메모이제이션 없이 w(15, 15, 15)를 계산하면:

  • 같은 (a, b, c) 조합이 수백만 번 중복 계산됨
  • 시간 복잡도가 지수적으로 증가

메모이제이션 사용 시

  • 각 고유한 (a, b, c) 조합을 한 번만 계산
  • 이후에는 저장된 값을 재사용
  • 시간 복잡도: O(21 × 21 × 21) = O(9261) (a, b, c가 20 이하로 제한되므로)

해결 방법

메모이제이션을 사용하여 재귀 함수를 최적화합니다:

  1. 딕셔너리를 사용하여 계산 결과를 저장
  2. 함수 호출 시 이미 계산한 결과가 있으면 반환
  3. 없으면 계산하고 딕셔너리에 저장

코드 구현

# 메모이제이션을 위한 딕셔너리
wd = {}
 
def w(a: int, b: int, c: int):
    global wd
    
    # 기저 조건 1
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    
    # 기저 조건 2
    if a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
    
    # 메모이제이션: 이미 계산한 결과가 있으면 반환
    if (a, b, c) in wd:
        return wd[(a, b, c)]
    
    # 재귀 호출
    if a < b and b < c:
        result = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    else:
        result = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
    
    # 결과를 메모에 저장
    wd[(a, b, c)] = result
    return result
 
# 입력 처리
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. 메모이제이션 딕셔너리: wd는 (a, b, c) 튜플을 키로, 계산 결과를 값으로 저장합니다.

  2. 기저 조건 처리:

    • a <= 0 or b <= 0 or c <= 0: 1 반환
    • a > 20 or b > 20 or c > 20: w(20, 20, 20) 호출

  3. 메모이제이션 체크: (a, b, c) in wd로 이미 계산한 결과가 있는지 확인합니다.

  4. 재귀 호출: 조건에 따라 적절한 재귀 호출을 수행합니다.

  5. 결과 저장: 계산한 결과를 딕셔너리에 저장하여 다음에 재사용합니다.

예제 동작 과정

w(1, 1, 1) 계산:

w(1, 1, 1)
  → else 조건 (a >= b or b >= c)
  → w(0, 1, 1) + w(0, 0, 1) + w(0, 1, 0) - w(0, 0, 0)
    → 모두 기저 조건 (a <= 0) → 1 반환
  → 1 + 1 + 1 - 1 = 2
  → wd[(1, 1, 1)] = 2 저장

w(2, 2, 2) 계산:

  • w(1, 2, 2), w(1, 1, 2) 등을 계산
  • w(1, 1, 1)은 이미 계산되어 있으므로 재사용
  • 최종 결과: 4

성능 비교

방법w(15, 15, 15) 계산 시간
메모이제이션 없이수 초 ~ 수 분 (시간 초과)
메모이제이션 사용수 밀리초

메모이제이션을 사용하면 수천 배 빠르게 계산할 수 있습니다!

주의사항

Note

원래 제공된 코드에서는 wd = {(1, 1, 1): 2}로 초기화되어 있었는데, 이는 불필요합니다. 메모이제이션은 함수 내에서 자동으로 처리되므로 초기값을 설정할 필요가 없습니다.

관련 알고리즘

그래프 뷰

백링크