[백준_9184번] 신나는 함수 실행

https://www.acmicpc.net/problem/9184

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인 경우는 입력의 마지막을 제외하면 없다.

 

[코드]

import java.util.Scanner;
/*
 * 미모제이션?
 * 처음 방문하는 재귀라면 계산을 통해 얻은 값을 메모리에 저장(기록)하고, 
 * 이 후 재방문을 할 경우 다시 계산하는 것이 아닌 저장 된 값을 사용
 */
public class BaekJoon_9184 {
	/*
	 * 함수 w에서 a, b, c 중 20이 넘어가게 되면 w(20, 20, 20)을 호출하고,
	 * 0 이하일 경우는 1을 반환하기 때문에
	 * 각 배열의 크기가 21 (0~20)을 넘기지 않는다.
	 */
	static int[][][] dp=new int[21][21][21];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		while(true) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			int c=sc.nextInt();
			
			if(a==-1&&b==-1&&c==-1) break;
			
			System.out.println("w("+a+", "+b+", "+c+")"+" = "+w(a,b,c));
		}
	}
	public static int w(int a, int b, int c) {
		// a,b,c가 0 초과 20 이하면서 저장한 값이 있으면 반환
		if(a>=0&&a<=20&&b>=0&&b<=20&&c>=0&&c<=20) {
			if(dp[a][b][c]!=0) 
				return dp[a][b][c];
		}
		if(a<=0||b<=0||c<=0) 
				return 1;
		//20을 초과하는 a, b, c 값은 20으로 조정되기 때문에 d[20][20][20]에 할당
		else 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);
	}
}

 

[고찰]

앞선 문제와 크게 다르지 않은 문제였다. 이미 계산되어 저장된 값이라면 배열 값을 return해 주고 아니라면 조건에 따라 계산한 값을 배열에 저장하면 되는 문제이다. 다만 a, b, c의 값이 모두 20을 넘을 수 없기 때문에 dp 배열의 값은 21 이하의 3차원 배열로 선언하면 된다는 점만 주의하면 어렵지 않게 해결할 수 있었다.