[코딩테스트] 백준 - 신나는 함수 실행

백준 - 신나는 함수 실행 9184번 [3일차]

시간제한	메모리 제한
1초	128MB

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

 

 

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

 

 

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

 

 

나의코드

package day3;

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

public class Solution4 {
    static int [][][] num = 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();

        while (true){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

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

            sb.append("w(" + a + ", " + b + ", " + c + ") = ").append(dp(a ,b ,c)).append('\n');
        }
        System.out.println(sb);
    }

    // -> 동적 프로그래밍
    static int dp(int a, int b, int c){

        // 기저 조건: a, b, c 중 하나라도 0 이하일 때 1을 반환
        if(a <= 0 || b <= 0 || c <= 0){
            return 1;
        }

        // 기저 조건: a, b, c 중 하나라도 20을 초과할 때 w(20, 20, 20)을 호출
        if(a > 20 || b > 20 || c > 20){
            return dp(20,20,20);
        }

        // 메모이제이션: 이미 계산된 값이 있는 경우 그 값을 반환
        if(num[a][b][c] != 0){
            return num[a][b][c];
        }

        // a < b < c 인 경우의 재귀 호출
        if(a < b && b < c){
            num[a][b][c] = dp(a, b, c - 1) + dp(a, b - 1, c - 1) - dp(a, b - 1, c);
        }else{
            // 그 외의 경우에 대한 재귀 호출
            num[a][b][c] = dp(a - 1, b, c) + dp(a - 1, b - 1, c) + dp(a - 1, b, c - 1) - dp(a - 1, b - 1, c - 1);
        }

        // 계산된 값을 반환
        return num[a][b][c];
    }
    // 똑같이 재귀를 쓰지만 메모지네이션 활용
    // 처음 방문하는 재귀라면 계산을 통해 얻은 값을 메모리에 저장하고, 이후 재방문 할 경우 다시 계산하는 것이 아닌 저장된 값을 가지고 오는방법
    // 동적 프로그래밍
    //


}