백준 4811번 알약 (JAVA)

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

4811번: 알약

 

저는 해당 문제를 DP를 통해 문제를 해결하였습니다.

dp를 통해 한번은 알약을 쪼개고 하나는 쪼개진 알약을 먹는 경우의 수를 구하고 저장하였습니다.

저는 dp[depth][cnt] (cnt는 온전한 알약의 개수)로 표현하였습니다.

depth가 2*cnt보다 크거나, cnt가 0 (온전한 알약의 개수)라면 쪼개진 반개의 알약을 먹는 경우를 추가 

cnt가 0보다 크면 알약을 쪼개는 것을 구하여 문제를 해결하였습니다.

 

package BOJ.dp;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.function.Function;

public class BOJ_4811 {
    private static final int FINISH = 0;
    private static final int SIZE = 30;
    private static final int NOT_VALID = -1;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String, Integer> stoi = Integer::parseInt;
        long[][] dp = new long[2*SIZE+1][SIZE+1];
        for(int i = 0 ; i <= 2*SIZE ; i++){
            Arrays.fill(dp[i],NOT_VALID);
        }
        while(true){
            int num = stoi.apply(br.readLine());
            if(num == FINISH){
                break;
            }
            long result = cal(2*num, num, dp, num);
            System.out.println(result);
        }
    }

    private static long cal(int depth,int cnt,long[][] dp,int n) {
        if(depth == 0){
            return 1;
        }
        if( dp[depth][cnt] != NOT_VALID){
            return dp[depth][cnt];
        }
        long result = 0;
        if(depth > 2 * cnt || cnt == 0){
            result += cal(depth-1,cnt,dp,n);
        }
        if(cnt > 0){
            result += cal(depth-1,cnt-1,dp,n); // 반으로 쪼개기
        }
        dp[depth][cnt] = result;
        return result;
    }
}