[백준/Java] 9184: 신나는 함수 실행

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

 

---

 

동적계획법의 특징은 대체로 재귀 + Memoization(메모이제이션)

 

📌 메모이제이션 Memoization

동일한 계산을 반복해야 할 때 사용

계산을 통해 얻은 값을 메모리에 저장(기록)하고,

이 후 같은 입력이 반복될 경우 다시 계산하는 것이 아닌 저장된 값을 사용함

 

🚀 참고
https://st-lab.tistory.com/190

 

---

 

풀이

1. a, b, c 세 개의 값이 들어오므로 계산값을 저장할 3차원 int 배열 생성 (memo[][][])
2. memo[a][b][c]에 접근했을 때 저장되어 있는 값이 있는 경우 해당 값 반환
3. 저장된 값이 없는 경우 새로 계산

 

코드

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

public class Main {

    static StringBuilder sb = new StringBuilder();
    static int[][][] memo = new int[21][21][21];

    static int w(int a, int b, int c) {
        if (a <= 0 || b <= 0 || c <= 0) {
            return 1;
        }

        if (a > 20 || b > 20 || c > 20) {
            return w(20, 20, 20);
        }

        if (memo[a][b][c] > 0) {
            return memo[a][b][c];
        }

        if (a < b && b < c) {
            memo[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
        } else {
            memo[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);
        }

        return memo[a][b][c];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        while (!(a == -1 && b == -1 && c == -1)) {
            sb.append("w(" + a + ", " + b + ", " + c + ") = ");
            sb.append(w(a, b, c));
            sb.append('\n');

            st = new StringTokenizer(br.readLine());

            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
        }

        System.out.println(sb);
    }
}