[2591번] 숫자 카드

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

dp를 이용하여 문제를 풀어보자.

우선 앞자리 값과 현재 값이 34 이하여야 하고 앞자리 값이 '0'이면 안된다.

이때 i가 1이면 0번째 1로 갱신해주고 i가 1이 아닐때부터는 dp[i - 2]번째 값을 dp[i]에 저장 할 수 있게 된다.

즉, 134에서 1,3,4 혹은 1,34가 될 수 있다는 의미가 된다.

최종적으로 현재 i값이 '0'이 아니면 이전 값을 더해와준다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#include <iostream> #include <cstdio> #include <string> #include <algorithm>   using namespace std;   int dp[100];   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];     }     printf("%d", dp[str.size() - 1]); }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus