Baekjoon 4811번 알약

문제

https://www.acmicpc.net/problem/4811

걸린 시간

01 : 44 : 00

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
using namespace std;

int n;
int bottle[31];
long long cache[31][60]; // 먹은 알약의 index, 약의 총량

long long dp(int idx, int size){
    // 기저 사례
    if(size == 0)
        return 1;
    // 메모이제이션
    long long& ret = cache[idx][size];
    if(ret != -1)
        return ret;
    // 재귀 호출
    ret = 0;
    for(int i = 1; i <= n; i++){
        if(bottle[i-1] < bottle[i]){
            if(bottle[i] != 0){
                bottle[i] -= 1;
                ret += dp(i, size-1);
                bottle[i] += 1;
            }
        }
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    while(true){
        cin >> n;
        if(n == 0) break;
        for(int i = 1; i <= n; i++)
            bottle[i] = 2;
        bottle[0] = 0;
        memset(cache, -1, sizeof(cache));
        cout << dp(0, 2*n) << "\n";
    }
    return 0;
}

먹은 알약의 인덱스, 현재 알약의 총량 을 상태로 가능한 문자열의 개수를 메모이제이션하면 시간 안에 해결할 수 있다.

가능한 경우의 수 가 int 형 범위를 초과하므로 long long 자료형을 사용해 주어야 하고, 중복되는 경우의 수를 제거하기 위해 먹으려는 알약이 이전 알약보다 클 경우에만 재귀 호출을 하도록 알고리즘을 작성해야 한다.