[맞음] 백준 4811 알약 c++ // 재귀dp, 경우의수는 +

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

 

1.의사코드

1. 알약을 1개꺼낸 경우 vs 반개꺼낸경우 계속 2분탐색이다.

2. 완탐? -> 2^30 -> 불가 -> dp?

3. 상태 : 큰알약갯수, 작은알약갯수 : 그때의 경우의수

4. 경우의수는 기저사례 -> return 1, 후 +하면 된다.

아래 그림과 같이 1이 리턴되고 거꾸로 타고오면서 그런 경우의 수가 모두 더해진다.

 

2. 전체코드

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

typedef long long ll;

ll dp[34][34];

//큰알약남은갯수, 반알약남은갯수 : 그상태일때, 경우의수
ll dfs(int a, int b) {
    if (a==0 && b==0) return 1;
    if (dp[a][b] != -1) return dp[a][b];

    dp[a][b] = 0;
    if (a > 0)
        dp[a][b] += dfs(a - 1, b + 1);
    if (b > 0)
        dp[a][b] += dfs(a, b - 1);
    return dp[a][b];
}

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

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

        memset(dp, -1, sizeof(dp));
        cout << dfs(tc,0)<<"\n";
    }


    return 0;
}

 

* 2회독 (25.3.15.) 맞음

• return 1
• and
• ret += dfs()
• 그림을 그리면서 return과 ret조건이 뭔지 찾는다.

 

• 종료조건
  • 오답 : a<0 or b<0 
  • 개선 : 약을 전부먹어야 종료조건 (a==0 and b==0)