[백준(Baekjoon)][자바(java)] 9184 : 신나는 함수 실행 / 동적 계획법 1

 

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

 

문제 풀이

 

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

public class Main {
	
	static int dp[][][];
	
	public static int w( int a, int b, int c ) {
		if( dp[a][b][c] > 0 )
			return dp[a][b][c];
		if( a <= 0 || b <= 0 || c <= 0 )
			return dp[a][b][c] = 1;
		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 );
		else
			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 );
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		int a, b, c, r = 0, ad, bd, cd;
		while( true ) {
			st = new StringTokenizer( br.readLine() );
			a = Integer.parseInt( st.nextToken() );
			b = Integer.parseInt( st.nextToken() );
			c = Integer.parseInt( st.nextToken() );
			if( a == -1 && b == -1 && c == -1 )
				break;
			sb.append( "w(" + a + ", " + b + ", " + c + ") = " );
			if( a <= 0 || b <= 0 || c <= 0 )
				r = 1;
			else if( a > 20 || b > 20 || c > 20 ) {
				dp = new int[21][21][21];
				r = w( 20, 20, 20 );
			}
			else {
				dp = new int[a+1][b+1][c+1];
				r = w( a, b, c );
			}
			sb.append( r + "\n" );
		}
		br.close();
		System.out.println( sb.toString() );
	}
}