[백준 16969] 차량 번호판 2 (C++)

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

문제

---

상도시의 차량 번호판 형식이 주어졌을 때, 가능한 차량 번호판의 개수를 구해보자.

• 번호판에 사용할 수 있는 숫자는 0, 1, 2, ..., 8, 9이다.
• 사용할 수 있는 문자는 a, b, c, d, ..., y, z이다.
• 차량 번호판의 형식은 최대 1,000,000글자이고, c와 d로 이루어진 문자열로 나타낼 수 있다.
• c는 문자가 위치하는 자리, d는 숫자가 위치하는 자리이다.
• 같은 문자 또는 숫자가 연속해서 2번 나타나면 안 된다.

예를 들어, 형식이 "cd"이면, a1, d4, h5, k4 등이 가능하다. 형식이 "dd"인 경우에 01, 10, 34, 69는 가능하지만, 00, 11, 55, 66은 같은 숫자가 2번 연속해서 불가능하다.

입력

---

첫째 줄에 차량 번호판의 형식이 주어진다. 형식은 길이가 1,000,000보다 작거나 같으며, c와 d로만 이루어져 있다.

 

출력

---

첫째 줄에 가능한 차량 번호판의 개수를 1,000,000,009로 나눈 나머지를 출력한다.

 

문제 풀이

---

수학 조합 문제.

 

c일 경우 26가지 선택을 할 수 있고, d일 경우 10가지 선택을 할 수 있다. 차량 번호판의 그 다음 문자가 같은 알파벳이라면, 선택 가능한 경우의 수에서 현재 선택한 알파벳 혹은 숫자는 선택 못하게 된다. 따라서 각각 25가지, 9가지 경우의 수가 존재하게 된다. 그 다음 문자가 같지 않다면 따로 제약 없으므로 각각 26가지, 10가지이다.

이를 입력받은 차량 번호판 문자열을 처음부터 끝까지 탐색하며 경우의 수를 계산하고, 오버플로우가 발생하지 않도록 계산이 끝날 때마다 1,000,000,009로 나누어 주면 된다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	string str;
	cin >> str;
	long long answer = 1;
	for (int i = 0; i < str.length(); i++)
	{

		if (i == 0)
		{
			if (str.at(i) == 'c')
			{
				answer *= 26;
			}
			else
			{
				answer *= 10;
			}
		}
		else
		{
			if (str.at(i) == 'c' && str.at(i-1) == str.at(i))
			{
				answer *= 25;
			}
			else if (str.at(i) == 'c')
			{
				answer *= 26;
			}
			else if (str.at(i) == 'd' && str.at(i - 1) == str.at(i))
			{
				answer *= 9;
			}
			else
			{
				answer *= 10;
			}
			answer %= 1000000009;
		}
	}
	cout << answer << "\n";
	return 0;
}