백준 4811 - 알약(C++)

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

4811번: 알약

N일이 주어졌을 때, 알약을 먹을 수 있는 방법의 경우를 구하는 문제입니다.

 

온전한 약을 꺼낸 뒤, 반을 먹고 반은 내려놓는 행위는 W, 반이 남은 알약을 꺼내 먹는 행위를 H라고 합니다.

 

1일만 약을 먹는다고 했을 때, 나올 수 있는 경우는

WH인 1개뿐이며

2일만 약을 먹는다고 했을 때, 나올 수 있는 경우는

WHWH, WWHH으로 2개가 됩니다.

3일의 경우에는

WHWHWH, WWHHWH, WHWWHH, WWWHHH, WWHWHH로 5개가 됩니다.

 

여기서 먼저 찾을 수 있는 것은

시작은 무조건 W, 끝은 무조건 H라는 점입니다.

 

그렇다면 3개의 경우는 나눠서 확인한다면

1. W -- H로 끝나는 경우

2. WW -- H로 끝나는 경우

3. WWW -- H로 끝나는 경우

이렇게 W기준으로 3개로 나눌 수 있습니다.

 

3일차의 경우에는 W, H가 각각 3개씩 무조건 있어야 한다는 것을 생각하면

각 경우마다 (W*2, H*2), (W*1, H*2), (W*0, H*2)의 경우를 더하는 것과 같아집니다.

 

그렇다면 4일의 경우에는 W*4, H*4개가 필요하니

W -- H / WW -- H / WWW -- H / WWWW -- H인 경우로 나눈 뒤, 

(W*3, H*3), (W*2, H*3), (W*1, H*3), (W*0, H*3)의 경우를 더해준 값이 됩니다.

 

따라서 [W의 개수][H의 개수]의 배열을 만든 뒤, 해당 값들을 저장해주면서 풀어주면 된다는 결론이 나옵니다.

 

저는 경우를 나눌 때, W를 기준으로 나눴기 때문에 W < H인 경우가 몇개가 나오는지만 확인해주면 됩니다.

W가 1개, H가 N개인 경우에는 W의 위치에 따라서 경우가 달라집니다. 이때 W는 N개의 곳에 위치할 수 있기에 [1][X] = X입니다.

 

W가 2인 경우에는 경우를 나눠서 생각해야합니다.

W*2, H*5인 경우라면, 해당 경우가 W or H로 시작하는 경우로 나눠야합니다.

따라서 W가 먼저 시작했다면, [1][5]의 경우가 될 것이며, H가 먼저 시작했다면 [2][4]의 경우가 될 것입니다. 이 둘을 더하면 됩니다.

 

이를 점화식으로 생각해보면

1. W < H인 경우 -> [X][Y]일 때, [X-1][Y] + [X][Y-1]의 값을 대입해준다.

2. W == H 인 경우 -> [X][Y]일 때, [0~X-1][Y-1]의 값을 전부 더해준다.

 

W개수/H개수	0	1	2	3	4	5	6
0	1	1	1	1	1	1	1
1		1	2	3	4	5	6
2			2	5	9	14	20
3				5	14	28	48
4					14	42	90
5						42	132
6							132

자세한 것은 코드를 참고해주세요.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <string>
#include <cmath>
#define INF 987654321

using namespace std;

long long pill[31][31];
int N;

void solve(){
    for(int i = 0; i <= 30; i++) pill[0][i] = 1;
    for(int i = 1; i <= 30; i++){
        for(int j = i; j <= 30; j++){
            if(i == j){
                for(int k = 0; k < i; k++) pill[i][j] += pill[k][j-1];
            }
            else{
                pill[i][j] = pill[i-1][j] + pill[i][j-1];
            }
        }
    }
}

int main(){
    cin.tie(0);
    cout.tie(0);
    solve();
    while(1){
        cin >> N;
        if(N == 0) break;
        cout << pill[N][N] << "\n";
    }
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요.