문제 출처

단계별로 풀어보기 > 동적 계획법 1 > 신나는 함수 호출
https://www.acmicpc.net/problem/9184

문제 설명

문제에 주어진 재귀 함수를 그대로 구현하게 되면 오랜 시간이 걸리므로, 시간안에 출력할 수 있도록 하라.

접근 방법

재귀 호출 + 메모이제이션을 이용하여 각 조건에 따라서 반환을 하면 된다.
1) a,b,c가 원하는 범위에 있고, dp 배열 안에 초기화 되어있다면 dp[a][b][c]를 return
2) a,b,c 중 하나라도 0보다 작거나 같으면 return 1
3) a,b,c 중 하나라도 20보다 크면 dp[20][20][20]을 반환한다. 단, dp[20][20][20]이 초기화 되지 않았을 경우를 대비하여 w(20, 20, 20)을 호출하여 넣어준다.
4) 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] = 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 한다.

이를 통해 w(a, b, c)를 호출하면 메모이제이션을 통해 원하는 값을 찾아가면서 dp에는 초기화되어 값을 찾는 속도가 빨라진다.

출처
https://st-lab.tistory.com/190

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

public class 신나는_함수_실행 {

    public static int dp[][][] = new int[21][21][21];

    public static int w(int a, int b, int c){

        if(a >= 0 && a <= 20 && b >= 0 && b <= 20 && c >= 0 && c <= 20 && dp[a][b][c] != 0) return dp[a][b][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(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);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        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 && b == -1 && c == -1) break;


            sb.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(")").append(" = ").append(w(a,b,c)).append("\n");


        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }

}

Review

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

public class 신나는_함수_실행_review {

    public static int[][][] dp = new int[21][21][21];

    public static int w(int a, int b, int c){


        if(a > 0 && a <= 20 && b > 0 && b <= 20 && c > 0 && c <= 20 && dp[a][b][c] != 0) return dp[a][b][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(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);
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        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 && b == -1 && c == -1){
                break;
            }

            sb.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ").append(w(a,b,c)).append("\n");

        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();

    }
}

알게된 점

처음에는 재귀를 이용하지 않고 풀려고 했으나, 이는 생각보다 복잡하였다
다른 사람들의 풀이를 보고 재귀 + 메모이제이션을 같이 이용하니 쉬운 문제였다.

문제푼 흔적

Review