[Algorithm]Baekjoon 2591번 :: 숫자카드

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
string target = "0";
int dp[43][38] = { 0 };
 
int DFS(int index, string curNumString, int addedNum)
{
    if (curNumString == target) return 1;
 
    int& result = dp[index][addedNum];
    if (result != -1) return result;
 
    result = 0;
 
    if (index + 1 < target.size() && target[index+1] != '0')
    {
         result += DFS(index + 1, curNumString + target[index + 1], target[index + 1] - '0');
    }
 
    if (index+2 < target.size() && target[index+1] != '0')
    {
        string addedNumString = { target[index + 1],target[index + 2] };
        int addedNum = stoi(addedNumString);
 
        if (addedNum <= 34)
        {
            curNumString = curNumString + addedNumString;
            result += DFS(index + 2, curNumString, addedNum);
        }
    }
 
    return result;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    string s;
    cin >> s;
    target += s;
 
    memset(dp, -1, sizeof(dp));
 
    cout << DFS(0, "0", 0);
}
 
 
 

 

타겟값에 맞춰 숫자를 하나씩 붙여넣을것이다.

근데 숫자카드는 1~34이기 때문에 두자리숫자를 붙이는경우도 고려해야 한다.

dp테이블은 다음과같다.

 

dp[인덱스][숫자]

 

예를들어 dp[3][5]이면, 3번째인덱스에 숫자5를 넣었을 경우, 타겟숫자를 만들 수 있는 모든 경우의 수이다.

dp[3][15]이면 3번째인덱스에 숫자 15를 넣었을경우가 된다.

15라는것은 두자리이니까 정상적으로 작동하나?라고 의문이 들 수 있지만, 어차피 코드를 보면알겠지만 두자리숫자를 넣을때는 index += 2를 하기때문에 잘 작동한다.

 

그리고 주의해야할 것은 입력으로 주어지는 타겟문자열에 숫자 0이 섞여있는 경우이다.

실제로 주어지는 숫자카드는 1 ~ 34로, 0은 존재하지 않는다.

그렇기때문에 탐색을 진행하던도중 다음숫자가 0일경우 탐색을 멈춰야 한다.

다만 두자리숫자일경우에는 일의자리에 0이들어오는건 가능하니 해당경우에만 탐색을 진행하면 된다.