[BOJ/백준][Gold5] 2591 : 숫자카드 (C++)

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

2591번: 숫자카드

 

 

[난이도] Gold5
[유형] DP

[풀이]
top-down dp를 이용해 해결할 수 있습니다.
dp[n] : s[n..N-1] 을 만들 수 있는 경우의 수.

1자리수를 선택하는 경우와 2자리수를 선택하는 경우를 나누어서 dp[n] 에 더해주면 됩니다.
두자리수 s[n..n+1]이 35보다 적은 경우 dp[n+2]를 더해줄 수 있습니다.
s[n]이 '0'인 경우는 예외처리를 해주어야 합니다.

 

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
using ll = long long;
int N;
ll dp[41];
string s;
ll sol(int n){
    if(n==N) return 1;
    ll& ret = dp[n];
    if(ret!=-1) return ret;
    ret=0;
    if(s[n]=='0') return 0;
    if(n<N-1) {
        string a = s.substr(n,2);
        if(stoi(a)<35){
            ret+=sol(n+2);
            if(a[1]=='0') return ret;
        }
    }
    ret+=sol(n+1);
    return ret;
}
int main(){
    cin >> s;
    N = s.size();
    memset(dp,-1,sizeof(dp));
    printf("%lld",sol(0));
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2591.cpp