[Olympiad] 지역본선 2005 초등부 : 숫자 카드 #2591

문제 링크

숫자 카드

문제 요약

• 1부터 34까지 수가 적힌 카드들이 있다.
• 카드의 숫자를 차례로 적어 놓은 것이 주어질 때, 가능한 카드의 배열이 모두 몇 개인지 구하는 프로그램을 작성해야 한다.
• 첫 줄에 카드의 숫자를 차례로 적어 놓은 것이 주어지며, 이것은 최대 40자 이하의 숫자로 이루어진다

Dynamic Programming

• 이 문제는 다이나믹 프로그래밍으로 풀이할 수 있다.
  • ex) 27123
• i가 1일 때
  • 27이므로 34보다 작고 십의자리가 2이다.
    1. 2, 7
    2. 27
• i가 2일 때
  • 71이므로 34보다 크다.
    1. 2, 7, 1
    2. 27, 1
• i가 3일 때
  • 12이므로 34보다 작고 십의자리가 1이다.
    1. 2, 7, 1, 2
    2. 2, 7, 12
    3. 27, 1, 2
    4. 27, 12
• 이런 식으로 Dynamic Programming을 이어나가면 된다.

문제 해답

#include <iostream>
#include <string>

using namespace std;

const int SIZE = 40 + 5;
int dp[SIZE];

int main() 
{
    string str;
    cin >> str;

    dp[0] = 1;
    for (int i = 1; i <  str.size(); i++) 
    {
        if (((str[i] - '0') + (str[i - 1] - '0') * 10) <= 34 && str[i - 1] != '0') 
        {
            if (i == 1) 
                dp[i] = 1;
            else 
                dp[i] = dp[i - 2];
        }
        if (str[i] != '0')
            dp[i] += dp[i - 1];
    }
    cout >> dp[str.size() - 1]);
    return 0;
}