문제
문제에서 주어진 3변수 재귀 함수 w(a, b, c)를 메모이제이션 DP로 효율화하는 문제이다. 주어진 재귀 규칙에 따라 w(a, b, c) 값을 계산하되, 동일한 인자로의 반복 호출을 캐시에서 바로 반환하여 시간을 단축한다. 입력으로 세 정수 a, b, c가 여러 줄 주어지며 -1 -1 -1이 입력될 때 종료한다.
입력
- 각 줄: 세 정수 a, b, c (범위 -50 이상 50 이하)
-1 -1 -1입력 시 종료
출력
각 입력에 대해 w(a, b, c) = [결과값] 형식으로 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 1 1 -1 -1 -1 | w(1, 1, 1) = 2 |
풀이
문제에서 제시된 재귀 함수를 그대로 구현하되, dp[a][b][c] 배열을 이용해 이미 계산한 결과를 저장해 중복 재귀를 방지한다. a, b, c가 20을 초과하면 w(20, 20, 20)과 동일하므로 범위를 제한한다.
- a, b, c 중 하나라도 0 이하이면 1을 반환한다.
- a, b, c 중 하나라도 20 초과이면
dp[20][20][20]값으로 제한한다. inRange(a, b, c)를 만족하고dp[a][b][c] != 0이면 캐시에서 바로 반환한다.a < b < c조건일 때와 그 외의 경우 각각 다른 점화식을 적용한다.
핵심 아이디어: a, b, c의 실질적 범위는 0~20으로 제한되어 있어 dp[21][21][21] 배열이면 모든 상태를 저장할 수 있다. inRange() 헬퍼로 배열 범위 초과를 방지하고, 계산된 값은 dp에 저장하여 동일 인자 재호출 시 즉시 반환한다.
코드
package com.ssafy.an.day049;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day45BOJ9184신나는함수실행DP정보기억 { // 9184 함수기억
static int dp[][][];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
StringBuilder sb = new StringBuilder();
dp = new int[21][21][21];// 20까지
while (true) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
if (a == -1 && b == -1 && c == -1) {
break;
}
sb.append("w(" + a + ", " + b + ", " + c + ") = ").append(w(a, b, c)).append('\n');
}
System.out.println(sb);
br.close();
}
static int w(int a, int b, int c) {
if (inRange(a, b, c) && dp[a][b][c] != 0) { // dp부분이 한번 방문했던 정보를 저장해서 사용하도록
return dp[a][b][c];
} // inRange() a,b,c가 20넘는 수가 있으니 체크해서 20값으로 바꿔야함.
if (a <= 0 || b <= 0 || c <= 0) {// 문제에 주어진 재귀
return 1;
}
if (a > 20 || b > 20 || c > 20) {
return dp[20][20][20] = w(20, 20, 20);
}
if (a < b && b < c) {
return 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] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1);
}
static boolean inRange(int a, int b, int c) {
return 0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20;
} // 주어지는 수는 50까지 인데, 20까지만 사용해야함.
}복잡도
- 시간: O(20³) — a, b, c 각각 최대 21가지 상태, 총 상태 수는 상수
- 공간: O(20³) — dp 배열 21 x 21 x 21