https://www.acmicpc.net/problem/9184
문제
> 재귀 호출만 생각하면 신이 난다! 아닌가요?
> 다음과 같은 재귀함수 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)를 출력하는 프로그램을 작성하시오.접근
재귀를 사용하여 문제에 주어진 함수를 구현하는데 문제에 주어진대로 그대로 구현하면 시간초과가 난다. 따라서 dp를 사용하여 함수내에서 중복되는 값은 미리 구해놓은 DP값을 불러와 사용해 연산을 줄인다.
문제해결
> 항상 참인 while문을 돌리며 a,b,c를 입력받는다.
> 이때, -1,-1,-1이 입력으로 들어오면 종료하므로 이를 처리해주고 아닐 시의 출력문을 작성한다.
> 함수 w를 메소드 W로 구현한다. 인자로 a,b,c를 가진다.
> 반복된 값을 처리하기위해 3차원 dp를 생성한다.
> 함수 기능에서 20보다 큰 값은 자동으로 20으로 초기화 되므로 dp의 크기는 a,b,c에 대해 각각 0부터 20까지 총 21이 된다.
> 1,2번 기능에 대해 구현하고 나머지 기능은 재귀로 값을 만들어낸다.
> 이때 반복된 값 등장의 처리를 위해 재귀 중 구해진 a,b,c에 대해 dp값이 존재한다면 더이상 계산하지 않고 이 값을 출력하도록 한다.
> 해당 dp값이 없다면 dp 값을 두 재귀문을 통해 구한다.
> 구했으면 해당 dp값을 반환한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
import java.util.function.IntUnaryOperator;
public class Main {
//9184번 신나는 함수 실행
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int[][][] dp = new int[21][21][21];
static public int W(int a, int b, int c) {
if(a <= 0 || b <= 0 || c <= 0) return 1;
if(a > 20 || b > 20 || c > 20) return W(20, 20, 20);
if(dp[a][b][c] != 0) return dp[a][b][c];
if(a < b && 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);
return dp[a][b][c];
}
public static void main(String[] args) throws IOException {
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(")
.append(a).append(", ")
.append(b).append(", ")
.append(c).append(") = ")
.append(W(a, b, c))
.append("\n");
}
System.out.print(sb);
}
}
후기
왜 dp를 쓰나 했었는데 하고나서 알았다. 문제에 말 그대로 매우 오랜시간이 걸린다고 써있다...
생각보다 많이 복잡했다.
