[백준, 자바, 9184번] 신나는 함수 실행

풀이

• 분명히 답도 잘 나오고 하는데 무슨 문제가 있는지 한참 고민했던 문제..
• 처음에는 뭔가 규칙을 찾아서 수학적으로 풀 수 있지 않을까 했는데
• 뭔가 변동되는 것들이 많아서 DP를 사용하기로 함
• 그런데 우선 DP를 어떻게 할까하고 생각해보다가
• 그냥 찾고자 하는 값이 11,1,5 라고 했을 때 
• 1115라는 문자로 변경 후 찾고 값을 넣어주면서 DP 값을 가져오도록 해서 해결했음
• 그런데 출력도 문제 없고 무슨 문제일까 계속 찾아봐도 답이 안나옴.
• 그래서 배열을 사용해서 해결하니까, 너무 쉽게 됨
• 이후 다시 원래 해결 방법으로 풀고자 다시 생각해보니
• 11, 1, 5 라고 할 때와 1, 11, 5와 1, 1, 15 같이 여러 개가 나올 수 있다는 것을 파악 후
• 문자로 변경하는 함수에 별도의 작업을 해주니 해결...
• 즉, 결론은 바보 같았다 

 

// 배열

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

public class Main {
    private static int[][][] mtx = new int[21][21][21];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        while (true) {
            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 && a == b && a == c) break;
            bw.write(String.format("w(%d, %d, %d) = %d", a, b, c, rec(a, b, c)) + "\n");
        }
        bw.flush();
    }

    public static int rec(int a, int b, int c) {
        if (check(a,b,c)&&mtx[a][b][c]!=0) return mtx[a][b][c];
        else if (a<=0 || b<=0 || c<=0) return 1;
        else if (a>20 || b>20 || c>20) return mtx[20][20][20]=rec(20, 20, 20);
        else if (a<b&&b<c) return mtx[a][b][c]=rec(a,b,c-1)+rec(a,b-1,c-1)-rec(a,b-1,c);
        else return mtx[a][b][c]=rec(a-1,b,c)+rec(a-1,b-1,c)+rec(a-1,b,c-1)-rec(a-1,b-1,c-1);
    }

    public static boolean check(int a, int b, int c) {
        return 0 <= a && a <= 20 && 0 <= b && b <= 20 && 0 <= c && c <= 20;
    }
}

 

 

// Map

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

public class Main {
    private static Map<String, Integer> dic = new HashMap<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        while (true) {
            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 && a == b && a == c) break;
            bw.write(String.format("w(%d, %d, %d) = %d", a, b, c, rec(a, b, c)) + "\n");
        }
        bw.flush();
    }

    public static int rec(int a, int b, int c) {
        if (a <= 0 || b <= 0 || c <= 0) return 1;
        else if (a > 20 || b > 20 || c > 20) {
            int r1;
            if (dic.containsKey("202020")) r1 = dic.get("202020");
            else {
                dic.put("202020", rec(20,20,20));
                r1 = dic.get("202020");
            }
            return r1;
        }
        else if (a < b && b < c) {
            int r1;
            int r2;
            int r3;
            if (dic.containsKey(s_change(a,b,c-1))) r1 = dic.get(s_change(a,b,c-1));
            else {
                dic.put(s_change(a,b,c-1), rec(a,b,c-1));
                r1 = dic.get(s_change(a,b,c-1));
            }
            if (dic.containsKey(s_change(a,b-1,c-1))) r2 = dic.get(s_change(a,b-1,c-1));
            else {
                dic.put(s_change(a,b-1,c-1), rec(a,b-1,c-1));
                r2 = dic.get(s_change(a,b-1,c-1));
            }
            if (dic.containsKey(s_change(a,b-1,c))) r3 = dic.get(s_change(a,b-1,c));
            else {
                dic.put(s_change(a,b-1,c), rec(a,b-1,c));
                r3 = dic.get(s_change(a,b-1,c));
            }
            return r1 + r2 - r3;
        } else {
            int r1;
            int r2;
            int r3;
            int r4;
            if (dic.containsKey(s_change(a-1,b,c))) r1 = dic.get(s_change(a-1,b,c));
            else {
                dic.put(s_change(a-1,b,c), rec(a-1,b,c));
                r1 = dic.get(s_change(a-1,b,c));
            }
            if (dic.containsKey(s_change(a-1,b-1,c))) r2 = dic.get(s_change(a-1,b-1,c));
            else {
                dic.put(s_change(a-1,b-1,c), rec(a-1,b-1,c));
                r2 = dic.get(s_change(a-1,b-1,c));
            }
            if (dic.containsKey(s_change(a-1,b,c-1))) r3 = dic.get(s_change(a-1,b,c-1));
            else {
                dic.put(s_change(a-1,b,c-1), rec(a-1,b,c-1));
                r3 = dic.get(s_change(a-1,b,c-1));
            }
            if (dic.containsKey(s_change(a-1,b-1,c-1))) r4 = dic.get(s_change(a-1,b-1,c-1));
            else {
                dic.put(s_change(a-1,b-1,c-1), rec(a-1,b-1,c-1));
                r4 = dic.get(s_change(a-1,b-1,c-1));
            }
            return r1 + r2 + r3 - r4;
        }
    }

    public static String s_change(int a, int b, int c) {
        String s_a = 10>a?"0"+a:String.valueOf(a);
        String s_b = 10>b?"0"+b:String.valueOf(b);
        String s_c = 10>c?"0"+c:String.valueOf(c);
        return s_a+s_b+s_c;
    }
}