[BOJ 9184] 신나는 함수 실행

10 Mar 2026

Reading time ~6 minutes

문제 요약

재귀 함수 w(a, b, c)가 다음 규칙으로 정의되어 있다.

a <= 0 또는 b <= 0 또는 c <= 0 → w = 1
a > 20 또는 b > 20 또는 c > 20 → w(a,b,c) = w(20,20,20)
a < b < c → w(a,b,c) = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
그 외 → w(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)

입력은 여러 줄로 주어지고, -1 -1 -1이 나오면 종료한다.

내가 처음 시도한 코드 (틀렸습니다)

나는 3차원 DP 배열을 크게 만들어서(-50..50) 전부 채우고, 그대로 인덱싱해서 출력하려고 했다.

a, b, c = 0, 0, 0

w = [[[1 for _ in range(101)] for _ in range(101)] for _ in range(101)]

for a in range(-50, 51):
    for b in range(-50, 51):
        for c in range(-50, 51):
            if a <= 0 or b <= 0 or c <= 0:
                w[a + 50][b + 50][c + 50] = 1
            elif a > 20 or b > 20 or c > 20:
                w[a + 50][b + 50][c + 50] = w[20 + 50][20 + 50][20 + 50]
            elif a < b and b < c:
                w[a + 50][b + 50][c + 50] = (
                    w[a + 50][b + 50][c-1 + 50]
                    + w[a + 50][b-1 + 50][c-1 + 50]
                    - w[a + 50][b-1 + 50][c + 50]
                )
            else:
                w[a + 50][b + 50][c + 50] = (
                    w[a-1 + 50][b + 50][c + 50]
                    + w[a-1 + 50][b-1 + 50][c + 50]
                    + w[a-1 + 50][b + 50][c-1 + 50]
                    - w[a-1 + 50][b-1 + 50][c-1 + 50]
                )

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+50][b+50][c+50]}")

내가 틀린 이유 (핵심)

1) `a > 20 or b > 20 or c > 20` 케이스를 “미리 채우는 방식”이 위험했다

규칙에 따르면 a > 20 or b > 20 or c > 20이면 항상 w(20,20,20)으로 “클램프”된다.

그런데 내 코드는 DP를 a=-50..50 순서로 채우면서, 예를 들어:

a = 1, b = 21, c = 21 같은 상태를 계산할 때
w[20+50][20+50][20+50](= w(20,20,20))을 참조한다.

문제는 이 시점(a=1)에는 아직 a=20까지 계산이 진행되지 않아서 w(20,20,20) 값이 제대로 채워져 있지 않다는 점이다.

즉, w(1,21,21) 같은 값이 원래는 w(20,20,20)이어야 하는데, 내 DP 테이블에서는 초기값(1) 을 참조해버려서 잘못 채워질 수 있다.

(입력에서 a는 50까지 가능하므로, w(1,50,50) 같은 케이스가 테스트에 포함되면 바로 오답이 난다.)

2) 결론: “클램프 케이스”는 DP 테이블을 채울 때가 아니라, 질의 처리에서 해주는 게 안전하다

GPT가 준 개선 코드: 어떻게 해결했나?

핵심 개선은 2가지다.

DP를 0..20 범위에서만 계산한다 (규칙상 그 범위만 있으면 충분)
입력을 받을 때 조건에 따라:
- <=0이면 1
- >20이면 dp[20][20][20]
- 그 외면 dp[a][b][c] 처럼 질의 시점에 클램프 처리를 한다.

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

for a in range(21):
    for b in range(21):
        for c in range(21):
            if a == 0 or b == 0 or c == 0:
                dp[a][b][c] = 1
            elif a < b and b < c:
                dp[a][b][c] = dp[a][b][c-1] + dp[a][b-1][c-1] - dp[a][b-1][c]
            else:
                dp[a][b][c] = dp[a-1][b][c] + dp[a-1][b-1][c] + dp[a-1][b][c-1] - dp[a-1][b-1][c-1]

while True:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break

    if a <= 0 or b <= 0 or c <= 0:
        ans = 1
    elif a > 20 or b > 20 or c > 20:
        ans = dp[20][20][20]
    else:
        ans = dp[a][b][c]

    print(f"w({a}, {b}, {c}) = {ans}")

DP 문제에서 유의할 점 (이번 문제로 정리)

상태 공간을 정확히 줄이기
이 문제는 사실상 0..20만 계산하면 된다. (그 이상은 모두 같은 값으로 클램프)
DP 채우는 순서(Topological order) 확인하기
“미리 큰 범위를 채우면서 아직 계산되지 않은 값을 참조”하면 오답이 날 수 있다.
클램프/예외 조건은 DP 계산 단계가 아니라 질의 단계에서 처리하면 안전한 경우가 많다
값 자체를 저장하는 DP는 배열 크기와 인덱스 실수가 가장 흔한 함정이라서, 가능한 한 문제 조건에 맞춰 범위를 단순화하는 게 좋다.