4811번

4811번 - 알약

처음에 쉽게 봤는데 정답률보다 어려웠던 것 같다 체감상..

W와 H의 관계에 대해서 처음에 잘 생각해보고 짜야 했다.

예시에 나와있듯이 엄청 큰 값이 나오므로 long long 형으로 값을 출력해야 한다.

처음에 재귀만 이용해서 완전탐색으로 풀었는데 시간초과가 나와서, DP로 고쳐서 문제를 풀었다.

D[w][h] = 알약이 W,H개 남았을 때, 만들 수 있는 글자의 수

로직은 W가 하나 없어지면 H가 하나 증가한다. 

그리고 기저 조건으로 W와 H가 결국 0 이 되면 하나의 경우가 생긴다. 이런식으로 다이나믹 프로그래밍을 이용해서 문제를 해결했다.

<정답 코드>

#include<iostream>
#include<string>
 
using namespace std;
int n;
long long ans;
long long D[31][31];
long long dfs(int w,int h)
{
    if (w < 0)
    {
        return 0;
    }
 
    if (w == 0 && h == 0)
    {
        return 1;
    }
 
    if (D[w][h] > 0)
    {
        return D[w][h];
    }
    
    if (w > 0)
    {
        D[w][h] += dfs(w - 1, h + 1);
    }
 
    if (h > 0)
    {
        D[w][h] += dfs(w, h - 1);
    }
 
    return D[w][h];
    
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
 
    while (cin >> n && n!=0)
    {
        ans = 0;
        
        cout << dfs(n, 0) <<"\n";
    }
 
    return 0;
}