백준 9184번 신나는 함수 실행

코드 1 (bottom-up)

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

public class Main {
    static int a;
    static int b;
    static int c;
    static int [][][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        dp = new int[21][21][21];
        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) return;

            int answer = 0;
            if(a<=0||b<=0||c<=0){
                System.out.println("w("+a+", "+b+", "+c+") = "+1);
                continue;
            }
            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] = w(i,j,k);
                    }
                }
            }
            answer = w(a,b,c);
            System.out.println("w("+a+", "+b+", "+c+") = "+answer);
        }
    }
    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]!=0){
            return dp[a][b][c];
        }
        if(a<b&&b<c){
            return w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
        }
        return w(a-1,b,c)+ w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
    }
}

풀이방법

📢 a,b,c 조건으로 위해 3차원 dp배열을 만드는것이 핵심이다.

1. 숫자 3개 중에 음수가 있다면, 조건에 따라 무조건 1이 나온다.
2. bottom up 방식으로 3차원 dp배열을 미리 채워넣는다.
   이후 재귀함수를 실행한다.
   이때, if(dp[a][b][c]!=0) return dp[a][b][c];
   이미 들어왔던 a,b,c 즉, 채워진 dp배열이라면, 해당 dp값을 리턴한다.
   이러한 방식으로 메모이제이션 해놓는다.
3. answer = w(a,b,c)를 구한다.

코드 2

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

public class ExcitingDefRun {
    static int a;
    static int b;
    static int c;
    static int [][][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        dp = new int[21][21][21];
        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) return;

            int answer = 0;
            if(a<=0||b<=0||c<=0){
                System.out.println("w("+a+", "+b+", "+c+") = "+1);
                continue;
            }
            answer = w(a,b,c);
            System.out.println("w("+a+", "+b+", "+c+") = "+answer);
        }
    }
    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 dp[20][20][20] = w(20,20,20);
        }
        if(dp[a][b][c]!=0){
            return dp[a][b][c];
        }
        if(a<b&&b<c){
            return 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] = w(a-1,b,c)+ w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
    }
}

풀이방법

1. top-down 방식으로 메모이제이션 하는데, 들어온 a,b,c값을 dp배열에 순차적으로 넣으면서 재귀함수를 실행한다.
2. answer값을 구한다.

시간 비교

top-down 방식이 시간복잡도가 더 빠르다.

후기

이문제는 Top-down으로 풀라고 만든문제다
첫번째 코드인 bottom-up방식은 for문으로 다 채우고 재귀함수를 다시 도는 방법인데, 두번 돌아야하므로 효율이 좋지 않다.
심지어 for문이 3중포문이므로 더 그렇다. 통과안되도 할말 없는코드.
두번째는 재귀함수를 돌면서 dp를 채우므로 한번에 같이 로직을 수행한다.
맨날 bottom-up만 써서 top-down 문제로만 풀어야 할때는 정작 잘 못하겠다.