[백준] 동적 계획법 (9184 : 신나는 함수 실행)

문제

---

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

9184번: 신나는 함수 실행

---

해설

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    static long w[][][];

    public static void main(String[] args) throws IOException {
        w = new long[51][51][51];
        w[0][0][0] = 1;

        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 = new StringBuilder();
            sb.append("w("+a+", "+b+", "+c+") = " + recur9184(a,b,c)).append("\n");
            bw.write(sb.toString());
            bw.flush();
        }
        bw.close();
    }

    private static long recur9184(int a, int b, int c){
        if(a <= 0 || b <= 0 || c <= 0)
            return w[0][0][0];
        if(w[a][b][c] != 0)
            return w[a][b][c];
        if (a > 20 || b > 20 || c > 20)
            return w[a][b][c] = recur9184(20, 20, 20);

        if (a < b && b < c)
            return w[a][b][c] = recur9184(a, b, c-1)+
                    recur9184(a,b-1, c-1)-
                    recur9184(a, b-1, c);

        return w[a][b][c] = recur9184(a - 1, b, c) +
                    recur9184(a - 1, b - 1, c) +
                    recur9184(a - 1, b, c - 1) -
                    recur9184(a - 1, b - 1, c - 1);
    }
}

이번 문제는 의사코드를 동적 계획법을 이용하도록 구현하는 문제이다.

a,b,c 가 입력되었을 때, 최종 결과를 얻기 위해서는 여러번의 재귀함수의 호출이 필요하다.

그런데,  진행하다보면 동일한 a, b, c의 값을 여러번 구해야하므로, 한번 계산했을 때 이를 저장해두고

나중에 다시 해당 결과값을 구해야할 때 구하지않고, 해당 값을 그대로 사용하면 된다!.

따라서, w[a][b][c]의 3차원 배열에 a,b,c의 값을 이용하여 값을 저장해두는 방식으로 문제를 해결할 수 있다.

---

결론

---

동적 계획법을 오랜만에 풀어보는데, 아직은 간단하게 해결할 수 있었다~!.

---