[백준] 2591 - 숫자카드

1. 문제 이해

입력으로는 40글자 이하의 숫자가 한줄로 주어진다.

EX) 27123

 

이 숫자는
1부터 34 까지 적힌 카드를 일렬로 나열해서 만들어낸 숫자이다. 이 때 카드를 나열하는 경우는 여러가지가 될 수 있다.

 

27123 의 경우

[ 2 ][ 7 ][ 1 ][ 2 ][ 3 ]

[ 2 ][ 7 ][ 12 ][ 3 ]

 

위 2가지 경우 이외에도 4가지 경우가 존재하여 총 6가지 경우의 수가 존재한다.

입력으로 받은 숫자를 만들어 낼 수 있는 카드의 배열의 경우의 수를 구하는 문제이다.

---

2. 문제 풀이

이 문제는 작은 문제로 쪼갤 수 있는 문제이다.

27123의 경우

2를 빼놓고 7123의 경우의 수를 구하고

27을 빼놓고 123의 경우의 수를 구할 수 있다.

27123의 정답 = 7123의 정답 + 123의 정답

즉, DP를 이용해서 풀 수 있다.

예시처럼 숫자 뒤에서부터 카드의 배열 수를 구한다. 그러면서 맨 앞 두개의 숫자를 합쳤을 때 34이하인지 아닌지만 구분하면 된다.

27123의 정답 = 7123의 정답 + 123의 정답

77123의 정답 = 123의 정답

이 때 유의해야 할 점은 0이다. 1부터 34까지라는 범위안에 있는 10, 20, 30 에 0이 사용된다. 이 0은 단독으로 사용될 수 없으므로 유의해야 한다.

101010의 경우

[ 10 ][ 10 ][ 10 ]

1가지 경우만 존재한다. 위 방법대로 숫자를 뒤에서부터 1개씩 늘려가면서 보면 맨 앞숫자가 0이되는 경우가 나올 것이다.

0이 맨 앞에 나오는 경우는 없으므로 경우의 수가 0이라고 생각하면 된다.

 

121010을 예시로 들면

0 : 0가지

10 : 1가지

010 : 0가지

1010: 1가지

21010 : 1가지

121010 : 2가지

---

3. 문제 코드

#include <iostream>
#include <cstring>
#DEFINE MAX_NUM 34
using namespace std;
char num[44];
int dp[44];

// 문자2개를 붙여서 숫자로 반환
int convertInt(char a, char b) {
    return ((a-'0') * 10) + (b-'0');
}


int main() {
    cin >> num;
    int len = strlen(num);


    dp[0] = 1; // 아래 반복문에서 i=2일때만 한번 사용됨. 정답을 위해 1로 둔다.
    dp[1] = num[len-1] == '0' ? 0 : 1; 

    if(len >= 2) {
        for(int i=2; i<=len; i++) {

            // 0인 경우 경우의 수 0가지
            if(num[len - i] == '0') {
                dp[i] = 0; continue;
            }

            int tmp = convertInt(num[len-i], num[len-i+1]);

            if( tmp <= MAX_NUM ) {
                dp[i] = dp[i-1]+dp[i-2];
            } else {
                dp[i] = dp[i-1];
            }

        }
    }
    cout << dp[len];
}