[BOJ] 백준 4811 : 알약 (java)

🧪 4811 알약

---

난이도 : 🌟 골드 5
유형 : 동적 프로그래밍 (DP)

4811번: 알약

 

📝 문제

---

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

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

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

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

 

입력

 

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

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

 

출력

 

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

 

🚧  주의할 점

---

1. 약의 개수는 30개 이하이고, 테스트 케이스가 최대 1000개에 값이 크기 때문에 모든 테스트 케이스마다 dp를 채우기 보다는 dp를 미리 채워서 메모이제이션 시켜두고 테스트케이스 값을 입력함으로써 결과를 구한다면 더 빠른 수행시간이 가능하다.

 

🧐 핵심 로직

---

H / W	0	1	2	3	4
0	x	1	1	1	1
1	x	1	2	3	4
2	x	x	2	5	9
3	x	x	x	5	14
4	x	x	x	x	14

 

1) h = 0 일 때 즉, w로만 문자열을 만드는 경우의 수는 1이고 표를 채우다보면 dp의 규칙이 보인다.

`dp[w][h] = dp[w][h-1] + dp[w-1][h];` 라는 규칙으로 dp[n][n]을 구하면된다.

 

💻 최종 코드 (152 ms)

---

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

public class Main {

    static int n;
    static long[][] dp;
    public static void main(String[] args) throws IOException {

//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        dp = new long[31][31];

        for (int i = 0; i <= 30; i++) {
            for (int j = 0; j <= 30; j++) {
                if (j > i) continue;
                else if (j == 0) dp[i][j] = 1;
                else dp[i][j] = dp[i][j-1] + dp[i-1][j];
            }
        }

        boolean checkCount = true;

        while (checkCount) {
            n = Integer.parseInt(br.readLine());

            if (n == 0) {
                checkCount = false;
                return;
            }

            System.out.println(dp[n][n]);
        }

        br.close();
    }
}