[JAVA]백준 9184번: 신나는 함수 실행

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

1. 문제 설명

 

재귀 함수 w(a, b, c)가 있는데 이 함수를 구현하는 것은 쉽다! 하지만 그대로 구현하면 값을 구하는데 오래 걸린다.

 

a, b, c가 주어졌을 때 w(a, b, c)를 출력하라.

 

2. 풀이

 

w(a,b,c) 함수의 구현과 메모이제이션을 합쳐서 구현하면 쉽게 풀 수 있는 문제이다.

 

a, b, c가 주어졌을 때 그 계산의 결과를 dp [a][b][c]에 저장해 두고

 

다음 a, b, c가 주어졌을 때 똑같은 배열을 재사용하여 이미 계산한 값이면 계산을 수행하지 않는다.

 

3. 코드

 

import java.io.*;
import java.util.*;

public class Main {

    public static int[][][] dp=new int[21][21][21];


    public static void main(String[] args) throws IOException {

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        int a,b,c;


        while(true){

            StringTokenizer 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;

            bw.write("w("+String.valueOf(a)+", "+String.valueOf(b)+", "+String.valueOf(c)+") = "+String.valueOf(W_make(a,b,c))+"\n");


        }

        bw.flush();
        bw.close();
        br.close();

    }

    public static int W_make(int a,int b,int c){

        if(a<=0 || b<=0 || c<=0)
            return 1;

        if(a>20 || b>20 || c>20)
            return W_make(20,20,20);

        if(dp[a][b][c]!=0)
            return dp[a][b][c];


        if(a<b && b<c)
            dp[a][b][c]=W_make(a,b,c-1)+W_make(a,b-1,c-1)-W_make(a,b-1,c);
        else
            dp[a][b][c]=W_make(a-1,b,c)+W_make(a-1,b-1,c)+W_make(a-1,b,c-1)-W_make(a-1,b-1,c-1);

        return dp[a][b][c];
    }



}