👨‍💻 문제

---

✍️ 풀이

🤔 생각

W는 온전한 알약을 꺼냈을 때의 문자이고,
H는 절반의 알약을 꺼냈을 때의 문자이다.

이것들로 만들 수 있는 문자열의 개수를 구한다는 것은 경우의 수를 구한다는 것과 같은 의미다.

우선 H는 W를 꺼내 절반을 쪼개 다시 넣기 전에는 절대 나올 수 없다.
이는 꺼낸 W의 수와 병에 든 H의 수가 같음을 의미한다.

또한 알약의 수는 N개 이므로 W와 H는 모두 꺼냈을 때 각각 N개씩 존재하게 된다.

꺼낸 알약의 상태를 정리하면 이러하다.

꺼낸 알약 H는 W보다 많을 수 없음 (언제든지) -> 첫 번째에 H가 나올 수 없는 이유
👉 H <= W

W와 H는 결국 각각 N개씩 나옴
👉 W <= N

👉 H <= W <= N

📈 DP 배열

처음엔 꺼낸 알약의 상태를 클래스로 정의해 1차원 배열로 풀 수 있을까 생각해보았다.
아무리 생각해보아도 해답은 나오지 않았고 그러던 중 2차원 배열이 떠올랐다.
N의 범위 또한 2차원 배열로 쓰기에 부담스럽지 않은 크기였다.

📈 DP

처음엔 무조건 W가 나오므로 아래와 같이 초기화를 한다.

n이 4일 때의 예시

H <= W <= N

위 규칙을 지키며 표를 채워나간다.

알약의 수가 N개라면 배열[N][N]이 알약을 뽑는 경우의 수가 된다.

    private static void dp() {
        arr[1][0] = 1;

        for (int w = 0; w <= MAX_N; w++) {
            for (int h = 0; h <= MAX_N; h++) {
                if (w < MAX_N) {
                    arr[w+1][h] += arr[w][h];
                }
                if (h < w) {
                    arr[w][h+1] += arr[w][h];
                }
//                System.out.printf("%8d", arr[w][h]);
            }
//            System.out.println();
        }
    }

표의 결과는 일정하기 때문에 항상 DP를 수행하지 않고,
N의 최댓값인 30으로 DP를 수행하여 배열을 완성시킨 후,
N이 입력되면 배열[N][N]만을 뽑아내면 된다.

---

📄 전체 소스코드

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

public class _4811 {

    private static final int MAX_N = 30;
    private static long[][] arr = new long[MAX_N + 1][MAX_N + 1];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        dp();
        StringBuilder sb = new StringBuilder();
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) {
                break;
            }
            sb.append(arr[n][n]);
            sb.append('\n');
        }
        System.out.print(sb);
    }

    private static void dp() {
        arr[1][0] = 1;

        for (int w = 0; w <= MAX_N; w++) {
            for (int h = 0; h <= MAX_N; h++) {
                if (w < MAX_N) {
                    arr[w+1][h] += arr[w][h];
                }
                if (h < w) {
                    arr[w][h+1] += arr[w][h];
                }
//                System.out.printf("%8d", arr[w][h]);
            }
//            System.out.println();
        }
    }

}