신나는 함수 실행

문제 정보

• 백준 실버 2
• DP
• 문제 링크

풀이

문제에서 점화식이 주어지므로 이를 그대로 사용해 재귀로 구현하면 된다. 다만 중복 호출이 많이 발생하므로 메모이제이션을 적용한다.

a,b,c의 유효 범위가 1부터 20까지로 제한되므로 int dp[21][21][21]을 사용한다.

코드

import java.io.*;
import java.util.*;
 
public class Main {
    private static int[][][] dp;
    public static void main(String[] args) throws IOException {
        dp = new int[21][21][21];
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int a = 0, b = 0, c = 0;
        
        StringBuilder sb = new StringBuilder();
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            
            if (a == -1 && b == -1 && c == -1)
                break;
            
            sb.append("w(")
                .append(a).append(", ")
                .append(b).append(", ")
                .append(c).append(") = ")
                .append(w(a, b, c))
                .append("\n");
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
    
    private 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) {
            dp[20][20][20] = w(20, 20, 20);
            return dp[20][20][20];
        }
        
        if (dp[a][b][c] != 0)
            return dp[a][b][c];        
        
        if (a < b && b < c) {
            dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
            return dp[a][b][c];
        }
        
        dp[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 dp[a][b][c];
            
    }
}