[백준 4811] 알약(Java)

문제 링크 : https://www.acmicpc.net/problem/4811

이 문제는 dp 문제로 문제의 규칙성을 파악하면 풀 수 있습니다.

이 문제의 핵심은 dp 배열을 어떤 식으로 설정하는가 입니다. 이 문제는 dp 배열을 이차원 배열로서 dp[W : 한 조각을 꺼낸 날][H : 반 조각을 꺼낸 날] 로 설정하면 됩니다.

전체적인 로직은 다음과 같습니다.

1. 현재 알약의 상태인 dp[N][0] 조건에서 시작해서 역순으로 진행한다.
2. 알약 한 개가 멀쩡히 존재할 경우 현재 조건은 알약 한 개를 쪼개고 반 개를 추가한 조건과 같은 경우이다.
3. 만약 알약 반 개가 하나 이상 존재하는 경우라면 한 개를 쪼개지 않고 반 개를 먹는 경우의 수를 더한다.
4. W가 0, 즉 모든 알약을 다 쪼갰을 경우 쪼갠 알약 먹는 경우밖에 없으므로 1을 리턴한다.
5. 현재 조건이 dp 배열에 저장되어 있다면 해당값을 리턴한다.

다음은 코드입니다.

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

public class Main{

    static int N;
    static long[][] dp = new long[31][31];

    static long eatPills(int w, int h){
        // 만약 현재 조건의 값이 dp 리스트에 저장되어있다면 해당값 리턴
        if(dp[w][h] != 0) return dp[w][h];

        // 만약 w가 0, 즉 모든 알약을 다 쪼갰을 경우 쪼갠 알약 먹는 경우밖에 없으므로 1 리턴
        if(w==0) return 1;

        // 알약 한 개가 멀쩡히 존재할 경우 현재 조건은 알약 한 개를 쪼개고 반 개를 추가한 조건과 같은 경우임
        dp[w][h] = eatPills(w-1,h+1);

        // 만약 알약 반 개가 하나 이상 존재하는 경우라면 한 개를 쪼개지 않고 반 개를 먹는 경우의 수를 추가
        if(h>0) dp[w][h] += eatPills(w,h-1);

        // 결과 리턴
        return dp[w][h];
    }

    public static void main(String[] args) throws Exception{
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true){
            N = Integer.parseInt(br.readLine());
            if(N==0) break;

            // 현재 날짜에서부터 역순으로 찾아가기
            long res = eatPills(N,0);
            sb.append(res);
            sb.append("\n");
        }
        System.out.println(sb);
    }
}