✅ dp

문제

1. 해결 로직

• 알약은 온전하거나 반 조각이거나 2가지 경우가 있는데 N이 최대 30이므로 모든 경우를 세어본다면 2^30으로 시간초과가 날 것이다.
• 온전한 알약 있는지 없는지, 반 조각 알약이 있는지 없는지에 따라 꺼내는 경우가 나누어진다.

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

int N;
long long dp[31][31]; // dp[w][h] : 온전한 알약 w, 반 조각 알약 h개 일때 만들 수 있는 문자열의 수

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    while(1){
        cin >> N;
        if(N == 0) break;

        for(int w=0;w<=N;w++){
            for(int h=0;h<=N;h++){
                if(w==0){ // 온전한 알약 w 가 없는 경우, 반 조각 알약을 먹는 경우 한가지 밖에 없음
                    dp[w][h] = 1;
                }
                else{ // 온전한 알약 w 가 있는 경우
                    if(h==0){ // 반 조각 알약 h 가 없을 경우, 온전한 알약 w를 반 먹고 반조각 하나 추가해주는 경우 밖에 없음
                        dp[w][h] = dp[w-1][1];
                    }
                    else{ // 이외에는 온전한 알약 w를 반 먹고 반조각 하나 추가하거나, 반조각 먹는 경우 2가지
                        dp[w][h] = dp[w-1][h+1] + dp[w][h-1];
                    }
                }
            }
        }

        cout << dp[N-1][1] << "\n"; // 첫날에 약 하나를 꺼내 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣음
    }

    return 0;
}

3. 시간 복잡도

$O(N^2)$

4. Review

int로 dp를 선언하면 N의 최댓값인 30을 넣어보면 이상한 값이 나온다.
따라서 보다 넓은 범위를 커버하기 위해 long long을 사용했다.

5. Reference

https://cpp-dev.tistory.com/68