백준 4811번 - 알약

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

DFS(재귀)로 약이 한 조각 남은게 없을때까지 호출해준 뒤에 모두 반조각이 남아있을 때 1을 리턴해주면 된다.

남은 반조각이 몇개가 되었든 계속해서 H를 보내는 경우만 남기 때문이다.

주의할 점은 값의 범위가 매우 크기 때문에 long long을 써줘야 한다.

또한, 시간초과가 나기 때문에 이전에 W,H의 개수에 따라 가능한 문자열의 개수를 저장한 뒤에 다시 호출하지 않도록 했다.

#include <iostream>
using namespace std;
 
int N;
long long dp[31][31]={0};
long long dfs(int W,int H){
    
    if(dp[W][H])
        return dp[W][H];
    
    if(W==0)
        return 1;
    
    dp[W][H] = dfs(W-1,H+1);
    if(H>0)
        dp[W][H] += dfs(W,H-1);
    
    return dp[W][H];
}
 
int main(){
    
    std::ios_base::sync_with_stdio(false);
    while(true){
        cin>>N;
        if(N==0)
            break;
        
        cout<<dfs(N,0)<<endl;
    }
    
    return 0;
}