백준 9184: 신나는 함수 실행
/ 9분 분량 / 문제 풀이
Silver II 난이도 문제를 C++로 풀이한 내용입니다. 재귀 함수 w(a,b,c)를 동적 계획법(DP)으로 효율적으로 계산하는 문제입니다.
문제 소개
백준 9184번 문제 신나는 함수 실행은 주어진 재귀 함수 w(a,b,c)의 값을 여러 쿼리에 대해 계산하는 문제입니다.
난이도: Silver II
사용 언어: C++
실행 시간: 8 ms
메모리: 2056 KB
문제 요약:
함수 w(a,b,c)는 다음과 같은 재귀 정의를 따릅니다:
w(a, b, c) = 1 (a≤0 or b≤0 or c≤0인 경우)
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) (a<b<c가 아닌 경우)
w(a, b, c) = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) (a<b<c인 경우)
입력으로 여러 (a,b,c)가 주어지며, -1 -1 -1이 입력될 때까지 각 쿼리의 w(a,b,c) 값을 출력합니다.
접근 방법
이 문제는 재귀 함수를 DP 테이블로 변환하는 전형적인 동적 계획법 문제입니다.
핵심 이해:
- a,b,c는 0~20 범위로 제한되어 있어 DP 테이블 크기가 작습니다 (21×21×21).
- 순수 재귀 구현 시 중복 계산이 심각하여 메모이제이션 또는 바텀업 DP가 필요합니다.
- 바텀업 DP 선택 이유: 입력 범위가 작고, 모든 상태를 순차적으로 채울 수 있어 재귀 호출 오버헤드 없이 효율적입니다.
- 의존 관계: dp[a][b][c]는 항상 더 작은 a,b,c 값만 참조하므로 3중 for문으로 안전하게 채울 수 있습니다.
풀이 과정
- Base Case 초기화: a≤0, b≤0, c≤0인 모든 경우 dp[a][b][c] = 1로 설정
- DP 테이블 채우기: a=1
20, b=120, c=1~20 순으로 반복하며 점화식 적용- a < b < c인 경우:
dp[a][b][c-1] + dp[a][b-1][c-1] - dp[a][b-1][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]
- a < b < c인 경우:
- 쿼리 처리:
- a,b,c ≤ 0 → 1 반환
- a,b,c > 20 → dp 반환
- 그 외 → dp[a][b][c] 반환
주의할 점:
- 입력 범위 초과 시 최대값(dp) 사용
- -1 -1 -1 입력 시 즉시 종료
- 3중 for문 순서가 중요 (작은 값부터 큰 값으로)
코드 설명
#include <bits/stdc++.h>
using namespace std;
// w(a,b,c) 함수의 DP 버전
// dp[a][b][c] = w(a,b,c)
// 9184 문제의 핵심: 재귀 정의를 DP 테이블로 치환
// dp 배열의 크기는 a, b, c가 0~20까지 가능하므로 21 21 21이다
int dp[21][21][21];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// ===============================
// 1. Base Case (재귀 종료 조건)
// a <= 0 or b <= 0 or c <= 0 -> w(a,b,c) = 1
// DP에서는 이걸 배열 값으로 미리 박아둔다
// 이렇게 하면 if문으로 재귀마다 체크할 필요가 없음
// ===============================
for (int a = 0; a <= 20; ++a)
for (int b = 0; b <= 20; ++b)
for (int c = 0; c <= 20; ++c)
if (a == 0 || b == 0 || c == 0)
dp[a][b][c] = 1;
// ===============================
// 2. Fill DP table (재귀 -> 반복 구조)
// dp[a][b][c]가 참조하는 것은 항상:
// - a-1, b-1, c-1 쪽 상태
// 즉, 모든 참조는 이전 상태만 보고 계산
// → 상태 그래프(의존 그래프)는 DAG
// → 따라서 위상 정렬 순서대로 계산 가능
// 3중 for문이 바로 이 위상 정렬
// ===============================
for (int a = 1; a <= 20; ++a) {
for (int b = 1; b <= 20; ++b) {
for (int c = 1; c <= 20; ++c) {
// ===============================
// 3. 점화식 (재귀를 DP로 치환)
// a < b < c 인 경우:
// dp[a][b][c] = dp[a][b][c-1] + dp[a][b-1][c-1] - dp[a][b-1][c]
// otherwise:
// 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]
// ===============================
if (a < b && 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];
}
}
}
}
// ===============================
// 4. 입력 처리
// -1 -1 -1 이 들어오면 종료
// DP 구현의 핵심:
// - a,b,c <= 0 -> 바로 1 반환
// - a,b,c > 20 -> dp[20][20][20] 반환
// - 나머지는 이미 채워둔 dp[a][b][c] 반환
// ===============================
int a, b, c;
while (cin >> a >> b >> c) {
if (a == -1 && b == -1 && c == -1)
break;
int ans;
if (a <= 0 || b <= 0 || c <= 0) // base case
ans = 1;
else if (a > 20 || b > 20 || c > 20) // 범위 초과 -> 최대값 참조
ans = dp[20][20][20];
else
ans = dp[a][b][c]; // DP 테이블에서 바로 꺼내기
cout << "w(" << a << ", " << b << ", " << c << ") = " << ans << "\n";
}
return 0;
}
복잡도 분석
- 시간 복잡도: O(20³) = O(8,000)
- DP 테이블 채우기: 21×21×21 반복
- 쿼리 처리: O(1) (미리 계산된 값 조회)
- 공간 복잡도: O(21³) = O(8,000) ≈ 64KB (int 4바이트 기준)
최적화 효과: 순수 재귀로 구현 시 지수시간(O(3^(a+b+c)))이지만, DP로 상수시간으로 단축.
배운 점
- 재귀 → DP 변환 패턴: 점화식 파악 → Base Case → 상태 의존 그래프 → 위상순 반복문.
- 범위 제한 활용: a,b,c≤20처럼 작은 범위에서 3차원 DP 테이블 사용이 효과적.
- 입력 범위 초과 처리: 문제에서 명시하지 않은 경우도 고려 (a>20 → dp).
- 다른 문제 적용 팁: 다차원 DP, 상태가 DAG인 경우 바텀업 방식 우선 고려. 비슷한 문제: BOJ 1563, 1904 등.