[BOJ / C++] 2591번 : 숫자 카드

문제

1부터 34까지 수가 적힌 카드가 충분히 많이 있다. 이들 중 몇 장을 일렬로 늘어놓고, 그 숫자를 차례로 적었다. 예를 들어 아래와 같이 카드가 놓인 경우 숫자를 차례로 적으면 27123이 된다.

나중에, 적어 놓은 것에 맞게 다시 카드를 늘어놓으려고 보니, 방법이 여러 가지일 수 있다는 것을 알았다. 예를 들어 27123의 경우 아래와 같이 여섯 가지 다른 방법이 있다.

카드의 숫자를 차례로 적어 놓은 것이 주어질 때, 위와 같이 그것을 가지고 거꾸로 카드의 배열을 찾으려고 한다. 가능한 카드의 배열이 모두 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫 줄에 카드의 숫자를 차례로 적어 놓은 것이 주어지며, 이것은 최대 40자 이하의 숫자로 이루어진다.

출력

첫 줄에 가능한 카드 배열이 몇 개인지를 출력한다.

Solved.ac 레벨

골드 V

풀이

간만에 머리가 빙글빙글 돌아가서 어지러웠던 문제.

DP 뇌는 언제쯤 활성화가 될까.

 

- 문자열로 수열을 입력받음 (str)

- dp[i]는 수열 0 ~ i - 1번째까지의 수를 숫자카드로 만드는 경우의 수

- dp[0] = 1, dp[1] = 1로 초기화. (1개의 수열을 숫자카드로 만드는 경우의 수는 1가지 밖에 없음.)

- dp[2], 두 자리 수를 숫자카드로 만드는 경우의 수부터 탐색.

 

* 예제에서는 숫자 0이 포함되지 않아 예제만으로 보면 헷갈릴 가능성이 있었다.

 

예제 27123을 토대로 과정을 풀이해본다.

 

1. dp[1]

'2'를 숫자카드로 만드는 경우.

위에서 기술했던대로 1가지 뿐이므로 1로 초기화

 

2. dp[2]

'27'을 숫자카드로 만드는 경우.

 

2 - 1.

먼저 현재 str의 자리, str[1]부터 생각해본다. (문자열의 인덱스이기 때문에 -1)

str[1]은 7이며, 0이 아니므로 각각 숫자카드 1장으로 만들 수 있는 경우의 수, 즉 dp[1]의 경우의 수로 초기화를 해준다.

-> dp[2] = dp[1] => 1

 

2 - 2.

다음으로는 두 자리 수가 34 이하여서 한 장의 카드로 구현이 가능한지 생각해본다.

str[0] * 10 + str[1] = 27 이 34이하이면서, str[0]이 0이 아니기 때문에 한 장의 카드로 구현이 가능하다.

str[0]이 0이라면 02, 07 같은 두 자리 숫자가 34 이하임을 만족시킬 수 있으며, 0 카드는 존재하지 않기 때문이다.

이는 0장의 카드를 만드는 경우의 수에 27 카드 1장을 사용하는 경우의 수를 더해주면 된다.

-> dp[2] += dp[0] => 1 + 1 = > 2

 

3. dp[3]

'271'을 숫자카드로 만드는 경우.

 

3 - 1.

2 - 1과 마찬가지로 현재 str의 자리, str[2]부터 생각해보자.

str[2]는 1이며, 0이 아니므로 각각의 숫자카드 1장으로 '27'까지 만드는 경우의 수, 즉 dp[2]의 경우의 수로 초기화를 해준다.

-> dp[3] = dp[2] => 2

 

3 - 2.

다음으로는 두 자리 수가 34 이하인지 판단해본다.

str[1] * 10 + str[2] = 71이 34를 초과하므로 한 장의 카드로 구현할 수 없다.

따라서 27을 한 장의 카드로 만드는 경우 1가지만 존재하므로 dp[3]에는 더 이상의 변화는 존재하지 않는다.

 

4. dp[4]

'2712'를 숫자카드로 만드는 경우.

 

4 - 1. 

현재 str의 자리 str[3]은 2, 0이 아니므로 각각의 숫자카드 1장으로 271까지 만드는 경우의 수, 즉 dp[3]의 경우의 수로 초기화를 해준다.

-> dp[4] = dp[3] => 2

 

4 - 2.

다음으로 다시 두 자리 수가 34 이하인지 판단.

str[2] * 10 + str[3] = 12이 34 이하이므로 한 장의 카드로 구현할 수 있다.

따라서 '27' 까지를 만드는 경우 + '12'를 만드는 경우를 추가해준다.

dp[4] += dp[2] => 2 + 2 = 4

 

5. dp[5]

'27123'을 숫자카드로 만드는 경우.

 

5 - 1.

현재 str의 자리 str[4]는 3, 0이 아니므로 각각의 숫자카드로 2712까지 만드는 경우의 수, 즉 dp[4]의 경우의 수로 초기화한다.

-> dp[5] = dp[4] =>  4

 

5 - 2.

다음으로 다시 또 두 자리 수가 34 이하인지 판단.

str[3] * 10 + str[4] = 23이 34 이하이므로 한 장의 카드로 구현 가능.

따라서 '271' 까지를 만드는 경우 + '23'을 만드는 경우 추가

dp[5] += dp[3] => 4 + 2 = 6

 

따라서 답은 6이 되고, 점화식은 아래와 같다.

1. 현재 탐색 중인 문자열의 자리( i - 1) 가 0이 아닐 때
dp[i] = dp[i - 1]

2. 현재 탐색 중인 문자열의 자리와 그 앞의 자리를 이용해 2자리 수를 만들었을 때 34 이하이며 이전의 수가 0이 아닐 때
dp[i] += dp[i - 1]

Code

#include<bits/stdc++.h>

using namespace std;

int dp[41];
string str;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> str;

    int ans = str.length();
    //문자열의 길이 저장.

    dp[0] = 1;
    dp[1] = 1;
    //1로 초기화

    for(int i = 2; i <= ans; i++) {
        if(str[i - 1] != '0') {
            dp[i] = dp[i - 1];
        }

        if(((str[i - 2] - '0') * 10) + (str[i - 1] - '0') <= 34 && str[i - 2] != '0') {
            dp[i] += dp[i - 2];
        }
    }

    cout << dp[ans] << "\n";



    return 0;
}

 

2591번: 숫자카드