[백준 2591번] 숫자카드 (C++)

문제링크 : https://www.acmicpc.net/problem/2591

2591번: 숫자카드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321; 

int dp[41];
int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    string s;
    cin >> s;

    dp[0]=1; //처음은 한개
    for(int i=1; i<s.size(); i++)
    {
        if(((s[i]-'0') + (s[i-1] - '0')*10) <=34 && s[i-1]!='0') //2자릿수 검토
        {
            if(i==1) dp[i]=1; //시작이 2글자
            else dp[i] = dp[i-2]; //2글자인 경우 추가
        }
        if(s[i]!='0') dp[i] += dp[i-1]; 
    }

    cout << dp[s.size()-1];
    return 0;
}

 

우선 입력이 문자열 형태이므로 이를 숫자로 변환하는 과정이 필요하다.

2자릿수인 경우 경우의 수가 추가되기에 현재 수 + 앞에 수가 범위안에 드는 두자릿수인지 체크를 해주어야 한다.

맨처음 dp[0]=1로 초기화해주는데, 이는 시작점이며 시작점은 무조건 한글자인 경우 1개이기 때문이다.

 

이후 반복문은 i=1부터 시작한다.

2자릿수이며, 범위 (<=34)에 맞는지 확인을 하고 만약 현재 i가 1이면 dp[i]=1로 초기화한다.

이는 시작이 2글자인 경우를 의미하며, 따라서 경우는 1가지 밖에 존재하지 않는다.

이외에는 현재 dp[i]=dp[i-2]를 하여 2글자 전의 경우의 수를 저장하도록 한다.

이를 마치고나서 현재 dp[i]에 dp[i-1]을 더해주도록 한다.

 

한글자인 경우는 전의 경우의 수를 그대로 유지하게 되는데 이는 직전 경우들에 대해 현재 숫자를 추가해준 것 뿐이므로 경우의 수가 늘어나지는 않는다.

2글자인 경우는 경우의 수가 늘어나게 되는데, 이는 앞서 dp[i]=dp[i-2]를 통해 2글자를 추가하기 전의 경우의 수를 현재 값에 저장하게 된다.

 

<27123>

2 
2, 7 / 27
2, 7, 1 / 27 , 1
2, 7, 1, 2 / 27, 1, 2 / 2, 7, 12 / 27, 12 (2자릿수인 경우 추가)