[백준 2591] 숫자카드 (C++)

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

문제

---

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

 

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

 

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

 

입력

---

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

 

출력

---

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

 

문제 풀이

---

dp를 이용한 문제.

백준 2302 극장 좌석과 유사하다.

 

문자열 끝까지 탐색하는데, i-1번 인덱스와 i번 인덱스를 함께 숫자로 변환했을 때 10이상 34이하이면 두 문자를 합쳐 두 자리 수를 만들 수 있다. 따라서 i-2번 인덱스까지 그대로 두고 두 문자를 합쳐 만든 경우의 수, i-1번 인덱스까지 그대로 두고 i번 인덱스의 수를 붙이는 경우의 수가 있다.

예를 들어 27123에서 인덱스 3인 2의 경우, 이전 인덱스 2와 함께 숫자로 변환하면 12이므로 27 / 12와, 271 / 2의 경우의 수가 가능해진다. i번 인덱스에서 이렇게 나누어지는 경우, 두 자리 수를 만들 때에는 dp[i-2]에 그대로 두 자리를 붙일 수 있고, 한 자리 수를 만들 때에는 dp[i-1]에 그대로 한 자리 수를 붙일 수 있으므로 dp[i] = dp[i-1] + dp[i-2]가 된다.

그런데 여기에서 i번째와 i+1번째 인덱스를 함께 숫자로 변환했을 때 10, 20, 30이 되는 경우가 있다. 이 때에는 i번째는 i+1번째 인덱스와 짝을 이루어 두 자리 숫자를 생성해야 하므로, i-1번 인덱스까지 그대로 두고 한자리 수를 붙이는 경우밖에 존재하지 않는다. 따라서 이 경우에는 dp[i] = dp[i-1]이 된다.

i번째 숫자가 0인 경우, 위의 10, 20, 30이 되는 경우에 해당하므로 경우의 수는 한가지밖에 존재하지 않는다. 따라서 dp[i] = dp[i-1]이 된다.

 

아래는 코드.

#include <iostream>
#include <string>
using namespace std;

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

	string str;
	cin >> str;
	int N = str.length();
	long long* dp = new long long[N];
	dp[0] = 1;
	for (int i = 1; i < N; i++)
	{
		if (str.at(i) == '0')
		{
			dp[i] = dp[i - 1];
			continue;
		}
		string prevStr = str.substr(i - 1, 2);
		int prevInt = stoi(prevStr);
		if (prevInt >= 10 && prevInt <= 34)
		{
			if (i == 1)
			{
				dp[i] = 2;
			}
			else
			{
				string currentStr = str.substr(i, 2);
				int currentInt = stoi(currentStr);
				if (currentInt == 10 || currentInt == 20 || currentInt == 30)
				{
					dp[i] = dp[i - 1];
				}
				else
				{
					dp[i] = dp[i - 1] + dp[i - 2];
				}
			}
		}
		else
		{
			dp[i] = dp[i - 1];
		}
	}
	cout << dp[N - 1] << "\n";
	return 0;
}