[백준 - 4811][Gold 5][해설 X] - 알약 (JAVA)

문제 링크

---

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

 

문제

---

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

 

입력

---

입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

 

출력

---

각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        long[][] dp = new long[31][31];

        //반조각만 남았을 때 먹을 수 있는 경우의 수는 1개이다.
        for(int i=0;i<dp.length;i++) {
            dp[0][i] = 1;
        }

        for(int full=1;full<=30;full++) {
            for(int half=0;half<30;half++) {
                //반쪽이 없어서 1개를 먹어야 되는경우
                if(half == 0) {
                    dp[full][half] = dp[full-1][half+1];
                }
                //반쪽과 1개짜리가 둘다 있는 경우
                else {
                    dp[full][half] = dp[full-1][half+1] + dp[full][half-1];
                }
            }
        }


        int N  = 0;

        while((N = Integer.parseInt(br.readLine()))!= 0) {
            //N개의 1개짜리 약과 0개의 반쪽짜리 약을 먹는 경우 출력
            System.out.println(dp[N][0]);
        }
    }
}

 

 

실행 결과

---

 

 

팁

---

• DP 점화식을 만들어 주고 코드를 진행하자
• DP 점화식을 만들 땐 조건이 무엇이 있는지 확인부터 해야한다.