[BOJ 9184번] 신나는 함수 실행 (Java)

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

9184번: 신나는 함수 실행

 

 

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

public class Main {

    static int[][][] arr;

    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));

        arr = new int [101][101][101];

        while(true){
            String[] s=br.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);

            if(a==-1&&b==-1&&c==-1) break;

            bw.write("w("+a+", "+b+", "+c+") = "+w(a, b, c)+"\n");
        }
        
        bw.flush();
        bw.close();
    }

    static int w(int a, int b, int c){
        if(a<=0||b<=0||c<=0) return 1;
        else if(a>20||b>20||c>20){
            if(arr[20][20][20]==0){
               int temp=w(20, 20, 20);
               arr[20][20][20]=temp;
               return temp;
            }
            else return arr[20][20][20];
        }
        else if(a<b&&b<c){
            if(arr[a][b][c]==0){
                int temp=w(a, b, c-1)+w(a, b-1, c-1)-w(a, b-1, c);
                arr[a][b][c]=temp;
                return temp;
            }
            else return arr[a][b][c];
        }
        else{
            if(arr[a][b][c]==0){
                int temp=w(a-1, b, c)+w(a-1, b-1, c)+w(a-1, b, c-1)-w(a-1, b-1, c-1);
                arr[a][b][c]=temp;
                return temp;
            }
            else return arr[a][b][c];
        }
    }

}

w라는 함수를 선언하고 문제에 나와 있는 재귀함수를 그대로 실행했습니다.

한 가지 다른 점은 arr이라는 삼중 배열을 선언하여 w 함수의 값을 저장해주었는데요, 

w(a, b, c) 함수의 값은 arr[a+50, b+50, c+50]에 저장을 했습니다.

만약 arr에 값이 있는 경우 arr 값을 사용하고 값이 없는 경우는 w 함수를 실행해 그 값을 arr에 저장하고 return하면서 사용을 했습니다.

즉, 재귀하여 계산한 값을 저장해 재사용한다는 점이 이 문제의 포인트였던 것 같습니다.