[Java] 백준 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)를 출력하는 프로그램을 작성하시오.

입력

입력은 세 정수 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

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	private static int [][][]dp=new int[21][21][21];		// dfs 안에서 a, b, c의 값이 0~20 사이만 존재하므로 배열 범위를 21로 정함
	
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		while(true) {
			StringTokenizer 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;
			
			int result=dfs(a, b, c);
			System.out.println("w("+a+", "+b+", "+c+") = "+result);
		}
		
	}

	private static int dfs(int a, int b, int c) {	// 주어진 재귀함수를 dp를 이용하여 중간값 저장
		if(a<=0 || b<=0 || c<=0) return 1;
		if(a>20 || b>20 || c>20) return dp[20][20][20]=dfs(20, 20, 20);
		if(dp[a][b][c]!=0) return dp[a][b][c];
		
		if(a<b && b<c) return dp[a][b][c]= dfs(a, b, c-1)+dfs(a, b-1, c-1)-dfs(a, b-1, c);
		return dp[a][b][c]=dfs(a-1, b, c)+dfs(a-1, b-1, c)+dfs(a-1, b, c-1)-dfs(a-1, b-1, c-1);
	}
}

재귀만을 이용하면 시간 초과가 발생하므로 dp를 이용하여 중간값을 저장해주어야 합니다. 여기서 while문 내에서 dp 배열을 만들어주었더니 메모리 초과가 발생하였습니다. 따라서 21*21 크기의 배열을 반복문이 돌 때마다 만들지 않고 처음에 한 번만 생성해주어야 합니다.