[백준]9184번 신나는 함수 실행(java)

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

9184번: 신나는 함수 실행

백준 9184번 신나는 함수 실행 문제 링크입니다.

핵심

동적 계획법을 사용하는 것인데, 재귀와 메모이제이션을 사용한다.

정답 코드

import java.util.Scanner;

public class Main{
    public static int[][][] arr = new int[21][21][21];
    public static void main(String[] args) {
        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.printf("w(%d, %d, %d) = %d \n",a,b,c,W(a,b,c));
        }
    }
    public static int W(int a,int b,int c){
        if(a<=0 || b<=0 || c<=0)return 1;

        if (Range(a,b,c) && arr[a][b][c]!=0){
            return arr[a][b][c];
        }
        if (a>20 || b>20 || c>20){
            return arr[20][20][20] = W(20,20,20);
        }
        if(a<b && b<c){
            return arr[a][b][c] =  W(a, b, c-1) + W(a, b-1, c-1) - W(a, b-1, c);
        }
        return arr[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);
    }
    static boolean Range(int a, int b, int c){
        return 0<=a && a<=20 && 0<=b && b<=20 && 0<=c && c<=20;
    }
}

해설

입력에 -1 -1 -1이 들어오면 실행을 종료한다.

문제에 있는 재귀 함수를 동적 계획법으로 바꾸기만 하면 된다.

처음 나온 배열의 값이면 저장하고, 이후 다시 그 배열의 값이 필요할 경우 저장된 값을 사용하는 것이다.

음수 또는 값이 초과될 경우  IndexOutOfBoundException가 발생하므로  Range라는 메서드를 사용하였다.

 

 

개선점이나 오류가 있다면, 댓글 부탁드립니다.