[백준 4811번] 알약 (C++)

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

4811번: 알약

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
ll dp[31][31]; //w(한 조각), h(반 조각)

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    while(1)
    {
        cin >> N;
        if(!N) break;
        for(int i=0; i<=30; i++) dp[0][i]=1; //초기값 (첫날 약 한개)
        for(int i=1; i<=30; i++) //w
        {
            for(int j=0; j<=30; j++) //h
            {
                if(!j) dp[i][0] = dp[i-1][1]; //직전 한조각 확정 -> [i-1][j+1]
                else dp[i][j] = dp[i-1][j+1] + dp[i][j-1]; //한조각 -> [i-1][j+1], 반조각 -> [i][j-1]
            }
        }
        
        cout << dp[N][0] << "\n";
    }

    return 0;
}

 

앞서 한 조각을 골랐는지, 반 조각을 골랐는지에 대해 염두를 두고 점화식을 세워야한다. (dp[w][h] : w 한 조각, h 반 조각)

기본적인 점화식은 dp[i-1][j+1] + dp[i][j-1]이다.

 

dp[i-1][j+1]의 경우는 한조각을 고른 경우다.

한 조각을 반으로 쪼개므로 w는 감소하고 반으로 쪼갬으로써 반조각이 생겼으므로 h가 증가한다.

dp[i][j-1]의 경우는 반 조각을 고른 경우다.

이 경우는 단순하게 h만 감소한다.

 

추가적으로 주의해야 할 것은 w가 0인 경우와 h가 0인 경우이다.

먼저 w가 0인 경우부터 보면 이는 초기화에 사용되기도 한다.

문제에 주어진 조건에 따라 처음 조각은 한조각으로 고정이고, 첫날 행동은 이 한 조각을 꺼내서 반은 먹고 반은 다시 집어 넣어서 dp[0][i]가 된 상태이다.

이 행동은 첫날 고정임에따라 경우의 수가 1가지로 초기값이 1로 정해진 것을 알 수 있다.

 

 

다음으로 h가 0인 경우를 보면 반조각이 없고 한 조각만 있는 상태이다.

현재 한 조각짜리만 있는 상태이므로 정해진 행동은이 한 조각를 먹고 남은 반을 다시 넣어두는 행위 뿐이다.

따라서 w가 감소하고 (한조각 갯수 감소) h가 증가한다. (반조각 갯수 증가)

 

이렇게 dp 식을 갱신하고 주어진 알약갯수인 N에 따른 dp[N][0]의 값을 출력시켜주면 된다.