(JAVA) 백준 9148번 : 신나는 함수 실행

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

9184번: 신나는 함수 실행

이 문제는 dp (동적계획법) 을 사용하고 함수는 기존의 함수를 그대로 사용하면 된다.

규칙이 있나 찾아보다가 재밌는 규칙을 찾아내서 그것도 사용해 보았다.

 

소스코드

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

public class Main
{
	// 20이상 50이상인 수가 하나라도 있으면 a,b,c = 20이 되기 때문에
    // 수의 범위 0~20
	static int[][][] dp = new int[21][21][21]; 
    
	public static void main(String[] args) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;		

		loop:
		while(true)
		{
			st = new StringTokenizer(br.readLine());

			while(st.hasMoreTokens())
			{
				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 loop;
				}

				sb.append("w("+a+", "+b+", "+c+") = "+w(a,b,c)+"\n");
			}
		}

		System.out.println(sb);
	}

	static int w(int a, int b, int c)
	{
		if(inRange(a,b,c) && dp[a][b][c] != 0)
		{
			return dp[a][b][c];
		}
		if(a<=0 || b<=0 || c<=0)
		{
			return 1;
		}
        // a,b,c 가 모두 같으면 2의 a제곱을 구하면 된다.
        // 하나만 다르고 두 수가 같아도 같은 수의 제곱을 구하면 된다!
		else if(a>20 || b>20 || c>20)
		{
			return dp[20][20][20] = (int)Math.pow(2,20);
		}
		else 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);
	}

	// 배열의 범위가 0~20이기 때문에 범위에 없는지부터 확인
	static boolean inRange(int a, int b, int c) 
	{
		return 0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20; 
	}
}