[코드그루] 94. 백준 9184번 : 신나는 함수 실행

// fail
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[] dp = new int[51];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        dp[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;
            dp[a + b + c] = wabc(a, b, c);
            sb.append("w(" + a + ", " + b + ", " + c + ") = " + dp[a + b + c] + "\n");
        }
        System.out.println(sb);
    }

    public static int wabc(int a, int b, int c) {
        if (a <= 0 || b <= 0 || c <= 0) {
            return 1;
        } else if (a > 20 || b > 20 || c > 20) {
            return wabc(20, 20, 20);
        } else if (a < b && b < c) {
            return wabc(a, b, c - 1) + wabc(a, b - 1, c - 1) - wabc(a, b - 1, c);
        } else {
            return wabc(a - 1, b, c) + wabc(a - 1, b - 1, c) + wabc(a - 1, b, c - 1) - wabc(a - 1, b - 1, c - 1);
        }
    }
}

 

 

처음에 int[][][] dp로 풀까 하다가 그렇게는 또 어떻게 푸는지 모르겠다!! dp[a + b + c]들은 값이 다 같지 않을까 라는 멍청한 생각을 함.당연히 답이 안 나옴…

 

문제에 나온 조건 따라가되 이게 이래서 dp구나를 알게 됨.

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[][][] dp = new int[21][21][21];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // dp 배열 모든 값을 -1로 설정
        for (int i = 0; i < 21; i++) {
            for (int j = 0; j < 21; j++) {
                for (int k = 0; k < 21; k++) {
                    dp[i][j][k] = -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.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ")
                    .append(w(a, b, c)).append("\n");
        }
        System.out.println(sb);
    }

    public 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 (dp[a][b][c] != -1) { // 이미 계산된 값일 경우 리턴
            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);
        } else {
            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];
    }
}

 

다음에 이런 문제는 절대 안 틀려야지!!!!!!!