[백준] 9184번 신나는 함수 실행 _ JAVA ( 주석 설명 )

1번

→

1. 입력값 a,b,c 에 해당하는 출력값을 구분하기 위해서 dp[][][] 3차원 배열 공간을 생성한다.

2. 각 조건에 맞게 계산을 진행하고, 계산한 출력값들을 dp 에 저장한다.

3. 재귀로 함수가 다시 호출될 시, 똑같은 입력에 대한 dp 에 저장된 값이 있으면 해당 값을 사용한다. (중복 계산 줄임)

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


public class Main {
    static int[][][] dp = new int[21][21][21]; //중복 계산을 막기 위해 중간 결과값들을 저장하기 위한 배열이다.

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int a = 0;
        int b = 0;
        int c = 0;

        while(true) { //-1,-1,-1 입력이 들어올 때까지 반복한다.
            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)
                break;

            //신나는 함수 실행
            sb.append("w(" + a + ", " + b + ", " + c + ") = ").append(fun(a ,b ,c)).append('\n');
        	
            /* String.format 을 이용하면 메모리와 시간 소모가 많이 된다.
            sb.append(String.format("w(%d, %d, %d) = %d", a, b, c, fun(a, b, c))).append('\n');
            */
        }

        System.out.println(sb); //입력으로 주어진 각각의 a,b,c에 대해서 fun(a,b,c)를 출력한다.
    }

    //Top-down 방식
    //Bottom-up 방식은 20*20*20의 전수조사(물론, 중간 결과값 저장으로 중복 계산이 많이 줄겠지만)를 해야하므로 비효율적이라고 예상된다.
    private static int fun(int a, int b, int c) {
        if (a <= 0 || b <= 0 || c <= 0)
            return 1;
        else if (a > 20 || b > 20 || c > 20){
            a=b=c=20;
        }
        if(dp[a][b][c]>1)
            return dp[a][b][c];

        else {
            if (a < b && b < c) {
                dp[a][b][c] = fun(a, b, c - 1) + fun(a, b - 1, c - 1) - fun(a, b - 1, c);
                return dp[a][b][c];
            }
            else {
                dp[a][b][c] = fun(a - 1, b, c) + fun(a - 1, b - 1, c) + fun(a - 1, b, c - 1) - fun(a - 1, b - 1, c - 1);
                return dp[a][b][c];
            }
        }
    }
}

1) String.format을 이용한 출력

 

2) 문자 조합을 이용한 출력