[JAVA] 백준 9184번 : 신나는 함수 실행

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

9184번: 신나는 함수 실행

---

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int a, b, c;
    static int[][][] dp = new int[21][21][21];
    static String[] input;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= 20; i++) {
            for (int j = 0; j <= 20; j++) {
                for (int k = 0; k <= 20; k++) {
                    if(i == 0 || j == 0 || k == 0)
                        dp[i][j][k] = 1;
                    else if (i < j && j < k){
                        dp[i][j][k] = dp[i][j][k - 1] + dp[i][j - 1][k - 1] - dp[i][j - 1][k];
                    }else
                        dp[i][j][k] = dp[i - 1][j][k] + dp[i - 1][j - 1][k] + dp[i - 1][j][k - 1] - dp[i - 1][j - 1][k - 1];
                }
            }
        }
        while (true) {
            input = br.readLine().split(" ");

            if(input[0].equals("-1") && input[1].equals("-1") && input[2].equals("-1")) break;
            a = Integer.parseInt(input[0]);
            b = Integer.parseInt(input[1]);
            c = Integer.parseInt(input[2]);

            //순서 주의...ㅡㅡ
            if(a <= 0 || b <= 0 || c <= 0)
                a = b = c = 0;
            else if(a > 20 || b > 20 || c > 20)
                a = b = c = 20;

            System.out.printf("w(%s, %s, %s) = %d\n", input[0], input[1], input[2], dp[a][b][c]);
        }
    }
}

💡 DP

풀이

• 여러 번 재귀를 반복하지 않기 위해 중간 값들을 dp배열에 저장하며 값을 미리 구해놓음
  • bottom-up 방식으로 채워나감
• 예제는 잘 나왔는데 3퍼센트에서 자꾸 틀렸습니다 나옴 🤨
  • 반례)  21 0 0 
  • 한참을 고민했는데... a, b, c 값 설정하는게 문제였음❗❗ => if문의 순서가 0이 먼저 와야 함
  • 문제 조건을 잘 살펴보면... a, b, c <= 0 인 조건 다음 > 20 조건이 나오는데 그대로 해야 함

a = Integer.parseInt(input[0]);
b = Integer.parseInt(input[1]);
c = Integer.parseInt(input[2]);

//오답 >> a = 20, b = 20, c = 20로 w(21, 0, 0) = w(20, 20, 20)으로 처리
if(a > 20 || b > 20 || c > 20)
	a = b = c = 0;
else if(a <= 0 || b <= 0 || c <= 0)
    a = b = c = 20;
//정답 >> a = 0, b = 0, c = 0로 w(21, 0, 0) = 1 이 돼야 함
if(a <= 0 || b <= 0 || c <= 0)
	a = b = c = 0;
else if(a > 20 || b > 20 || c > 20)
    a = b = c = 20;