BOJ)2591 숫자카드

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

DP로 생각하지않고 짜본 소스코드

n을 int나 long long 으로 호출하는 방법으로 하였을 시, 테스트 케이스들이 잘 출력되는 것처럼 보였다.

하지만, int형은 약 9자리의 정수를, long long형은 약 15자리의 정수를 갖을 수 있어, 그 이상 초과되는 자리들은 결과값이 0이 출력되었다.

이 점을 보완하고자, n을 문자열로 입력받아 정수로 변환하는 과정을 거쳐보았지만, 시간초과가 뜬다.

오답

#include <iostream> #include <algorithm> #include <cstring> #include <string> #include <queue> using namespace std; //long long n; char n[41]; int t = 0; int arr[41] = { 0 }; int arr_1_10[41][2]; int cnt = 0; void array_arr() { for (int i = t - 1; i >= 0; i--) { arr_1_10[i][0] = arr[i]; if (10 <= arr[i] * 10 + arr[i - 1] && arr[i] * 10 + arr[i - 1] <= 34 && i>0) { arr_1_10[i - 1][1] = arr[i] * 10 + arr[i - 1]; } } } void func(int num, int position) { if (num == t - 1 && position == 0 && arr_1_10[num][position] > 0) { cnt++; return; } if (num == t - 2 && position == 1 && arr_1_10[num][position] > 0) { cnt++; return; } if (position == 0 && arr_1_10[num][position] > 0) { func(num + 1, 0); func(num + 1, 1); } if (position == 1 && arr_1_10[num][position] > 0) { func(num + 2, 0); func(num + 2, 1); } return; } int main() { cin >> n; /*while (n) { arr[t] = n % 10; n /= 10; t++; }*/ t = strlen(n); for (int i = 0; i < t; i++) { arr[t - 1 - i] = n[i] - 48; } for (int i = 0; i < 42; i++) { memset(arr_1_10[i], -1, sizeof(int) * 2); } array_arr(); func(0, 0); func(0, 1); cout << cnt; }

DP로 사용하여 해결한 소스 코드

#include <iostream> #include <cstring> #include <algorithm> using namespace std; int main() { char n[45]; int num[45] = { 0 }; int dp[45] = { 0 }; cin >> n; for (int i = 0; i < strlen(n); i++) { num[i] = n[i] - '0'; } dp[0] = 1; for (int i = 0; i < strlen(n); i++) { if (num[i] != 0) { dp[i + 1] += dp[i]; if (10 <= num[i] * 10 + num[i + 1] && num[i] * 10 + num[i + 1] <= 34) { dp[i + 2] += dp[i]; } } } cout << dp[strlen(n)]; }