백준 [2591] "숫자 카드"

DP를 이용해 해결 할 수 있는 문제였다. 카드는 1~34까지의 숫자가 가능하기 때문에 현재 숫자가 0이 아니라면 이전의 값을 가져온다. 이유는 1자리 숫자는 결과에 영향을 주지 않기 때문이다.

이 문제의 핵심은 2자리 숫자를 조합하여 변경되는 경우의 수를 구해야만 한다.

I가 2이상(2자리 수가 가능할때 부터) 두자리 수가 10~34안에 들어오는지 검사하기 위해 이전 자리 *10 + 이번 자리를 통해 현재 숫자인 X를 구하고 만약 이전 자리와 현재 자리가 똑같다면 두 경우의 수를 더해준다. 이유는 그 두 자리 숫자를 하나로 묶어서 해석해야 하고, 그 전까지의 경우의 수를 사용해야 하기 때문이다.

#include <iostream>
using namespace std;

int dp[41];
char ch[41];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	dp[0] = 1;

	//1부터 34까지 수가 적힌 카드
	//숫자가 34를 넘기면 안된다는 뜻
	//34가 넘기 전까지는 조합이 가능하다.

	string s;
	cin >> s;

	for (int i = 0; i < s.size(); i++) {
		ch[i + 1] = s[i];
	}

	for (int i = 1; i <= s.size(); i++) {

		int k = ch[i] - '0';

		if (k != 0) {
			dp[i] = dp[i - 1];
		}

		if (i >= 2) {
			int x = (ch[i - 1] - '0') * 10 + k;
			if ( x >= 10 && x <= 34) {
				dp[i] = dp[i - 2] + dp[i];
			}
		}
	}

	cout << dp[s.size()];

	return 0;
}