🙆🏻‍♂️ DP 너, 정복당해라 [백준 2240번 - 알약 편]

문제

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

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

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

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

 

 

입력

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

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

 

 

출력

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

 

예제 입력1

6
1
4
2
3
30
0

 

예제 출력1

132
1
14
2
5
3814986502092304

 

정답 비율

68.542%

 

 

문제를 풀어볼까요! Let's go

 

문제 분석 및 사고 회로

문제에서 핵심 정보를 추출해보자.

병에서 약을 하나 꺼내고, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣어준다.

 

그 뒤로 계속 병에서 약을 하나 꺼낸다. 약이 한조각일지 반조각일지는 모른다.(랜덤)

2가지 경우로 나뉜다.(한조각, 반조각)

 

꺼낸 약이 반 조각이면 약을 먹고, 아닌 경우 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

즉, 한조각의 약을 먹을 경우 약의 총 갯수는 그대로 된다.(쪼개서 한조각은 먹고, 다른 조각은 병에 넣기 때문에)

 

한 조각을 껀내 날에는 W, 반 조각을 꺼낸 날에는 H를 보낸다.

이 문자들을 기록에서 2N일이 지나게 되면, 길이가 2N인 문자열이 만들어지는데, 가능한 서로 다른 문자열의 개수를 구하라

 

가능한 서로 다른 문자열의 개수를 예시를 들어보자.

 

약의 개수가 1개인 경우

 

1일 : 한조각을 꺼냄 - W

2일: 반조각을 꺼냄 - H

 

이렇게 되면 문자열이 "WH"가 되고, 정답은 1개가 된다.

 

 

약의 개수가 2개인 경우

 

1일 : 한조각을 꺼냄 - W

2일 : 반조각을 꺼냄 - H

3일 : 한조각을 꺼냄 - W

4일 : 반조각을 꺼냄 - H

 

문자열 결과 : "WHWH"

 

1일 : 한조각을 꺼냄 - W

2일 : 한조각을 꺼냄 - W

3일 : 반조각을 꺼냄 - H

4일 : 반조각을 꺼냄 - H

 

문자열 결과 : "WWHH"

 

나온 문자열이 WHWH, WWHH가 되므로 정답은 2개가 된다.

 

코드를 짜기 위한 접근

완전탐색을 하게될 경우 문자열의 총 길이 60에다가, 각 문자 W또는 H가 올 수 있기 때문에, 총 경우의 수는 2^60이 된다.

 

경우의 수가 너무 많다..!

경우의 수를 줄이기 위해서는 DP를 생각해 볼 수 있다.

 

알약을 꺼내는 상황은 다음과 같다.

 

반쪽자리 알약이 남아있는 경우

이 경우에는 반쪽자리 알약을 뽑는 경우와 한쪽자리 알약을 뽑는 경우로 나뉜다.

만약 반쪽자리 알약을 뽑은 경우라면 (한쪽짜리 알약 그대로)와 (반쪽짜리 알약 - 1)

한쪽자리 알약을 뽑은 경우라면 (한쪽짜리 알약 - 1)와 (반쪽짜리 알약 + 1)

 

반쪽자리 알약이 남아있지 않은 경우

이 경우에는 무조건 한쪽자리 알약을 뽑기 때문에, (한쪽자리 알약 - 1)과 (반쪽자리 + 1)이 된다.

 

풀이 코드1

package 백준.알약;

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

public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // dp[i][j]=i개의 완전한 알략, j개의 반절짜리 약이 남았을 때 조합의 수
        long[][] dp = new long[31][31];

        for (int i = 0; i <= 30; i++) { // 첫 시작은 한알을 먹고 시작하므로
            dp[0][i] = 1;
        }

        // i는 완전한 알약, j는 반절짜리 알약
        for (int i = 1; i <= 30; i++) {
            for (int j = 0; j < 30; j++) {
                if (j == 0) { // 반절짜리 알약이 없는 경우
                    dp[i][j] = dp[i - 1][j + 1];
                } else { // 반절짜리 알약이 있는 경우
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j + 1];
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) {
                break;
            }

            sb.append(dp[n][0]).append("\n");
        }

        bw.write(sb.toString());
        bw.flush();
        br.close();
        bw.close();
    }
}

 

출력 결과

 

풀이 코드2

 

재귀 호출 + DP 알고리즘 사용

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

public class Main {

    public static long[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // dp[i][j]=i개의 완전한 알략, j개의 반쪽짜리 약이 남았을 때 조합의 수

        dp = new long[31][31]; // 한쪽 or 반쪽

        while (true) {
            int num = Integer.parseInt(br.readLine());
            if (num == 0) {
                break;
            }

            sb.append(go(num, 0) + "\n");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    public static Long go(int whole, int notWhole) {

        if (whole == 0 && notWhole == 0) { // 알약이 남아있지 않은 경우
            return 1L;
        }

        if (dp[whole][notWhole] > 0) {
            return dp[whole][notWhole];
        }

        long ret = dp[whole][notWhole]; // 이전 값

        // 알약이 존재하고, 전체 알약을 꺼낸 경우
        if (whole > 0) { // 첫째날 약 하나를 꺼내므로 먼저 시작
            ret += go(whole - 1, notWhole + 1);
        }

        // 반쪽자리 알약이 존재하고, 반개짜리 알약을 꺼낸 경우
        if (notWhole > 0) {
            ret += go(whole, notWhole - 1);
        }

        dp[whole][notWhole] = ret; // dp 값 누적

        return ret;
    }
}

 

출력 결과