신나는 함수 실행(9184)

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

문제

다음과 같은 재귀함수 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)를 출력하는 프로그램을 작성하시오.

제한

-50 <= a, b, c <= 50

입력

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

출력

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

예제 입력

1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1

예제 출력

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

동적 계획법이란 문제의 최적해를 구하거나 답의 개수를 세는 과정에서 사용할 수 있는 알고리즘 설계 기법이다. 동적계획법을 사용하면 불필요한 계산을 줄이고, 효율적으로 최적 해를 찾을 수 있다.

"전체 문제를 작은 문제로 단순화한 다음 점화식으로 만들어 재귀적인 구조를 활용해서 전체 문제를 해결하는 방식"

1. 전체 문제를 작은 문제로 단순화 -> 부분 문제를 정의

2. 재귀적인 구조를 활용할 수 있는 점화식을 만듬 -> 점화식을 만듬

3. 작은 문제를 해결한 방법으로 전체 문제를 해결 -> 문제를 해결

*메모이제이션이란 함수의 값을 계산한 뒤, 계산된 값을 배열에 저장해두면 필요할 때마다 함수를 다시 호출하지 않고 값을 빠르게 가져올 수 있다.

풀이

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

public class Main{
    static int arr[][][];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        arr = new int[21][21][21];
        while(true){
            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(w(a,b,c)).append("\n");
        }
        System.out.println(sb);
    }
    public static int w(int a, int b, int c){
        if(0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20 &&arr[a][b][c] != 0)
            return arr[a][b][c];

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

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

}

백준

두번째 시도

import java.io.*;
public class Main
{ 
    static int[][][] arr = new int[21][21][21]; 
    public static void main(String[] args) throws Exception{ 
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    while(true){
    
        String[] tmp = bf.readLine().split(" ");
        int x = Integer.parseInt(tmp[0]);
        int y = Integer.parseInt(tmp[1]);
        int z = Integer.parseInt(tmp[2]);
        if(x==-1 && y==-1 && z==-1)
            break;
        bw.write("w("+x+", "+y+", "+z+") = "+fn(x, y, z) + "\n");
    }
    bw.flush();
}

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

    arr[a][b][c] = fn(a-1,b,c) + fn(a-1,b-1,c) + fn(a-1,b,c-1) - fn(a-1,b-1,c-1);
    return arr[a][b][c];


}
}

처음에 푼 방법은 이렇게 풀었는데 bf.readLine()에서 문자열 받을때는 굳이 split으로 나누지말고 java.util.*; 에 있는 StringTokenizer을 사용하자