Baekjoon2011-암호코드

백준 사이트 2011 - 암호코드 문제입니다.

1. 문제

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

---

2. Input , Output

---

3. 분류 및 난이도

DP문제입니다.
백준에서는 Sliver1의 난이도를 책정하고 있습니다.

---

4. 생각한 것들

• 예외처리가 무진장 많습니다. 특히 0에 대한 조건처리를 잘 해줘야합니다.
• stoi()함수를 쓸까 했지만 쓰는게 더 복잡할 것 같아서 쓰지 않았습니다.
• 2차원 DP를 사용했는데 dp[?][0] 은 그 자리에 한자리가 들어올 때, dp[?][1]은 그자리에 두자리가 들어올 때 입니다. ‘312’를 예를 들면 dp[3][0] = ‘31’ + ‘2’가 되는 거고 dp[3][1]은 ‘3’ + ‘12’ 가 되는 경우의 수 입니다.

---

5. code

#include<iostream>
#include<string>
using namespace std;
int dp[5001][2] = { 0, };

const int MOD = 1000000;

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

	string input;
	cin >> input;
	int countzero = 0;
	if (input[0]-48 == 0 )
	{
		cout << 0;
		return 0;
	}
	dp[0][0] = 1;
	dp[0][1] = 0;
	int numz = 0;
	size_t size = input.size()-1;
	for (size_t i = 1; i < input.size(); ++i)
	{
		if (input[i] - 48 == 0)
		{
			++countzero;
			if (countzero > 1)
			{
				cout << 0;
				return 0;
			}
		}
		else
			countzero = 0;
		
		//2개인 경우
		if (i >= 1)
		{
			if (input[i-1]-48!=0)//두자리 수 가능
			{
				numz = ((input[i - 1] - 48) * 10) +(input[i] - 48);
				if (numz > 0 && numz < 27)
				{
					if (i == 1)
						dp[i][1]++;
					else
						dp[i][1] = dp[i - 2][0] + dp[i - 2][1];
					dp[i][1] %= MOD;
				}
			}
			else
				dp[i][1] = 0;
		}

		//하나인 경우 나중에처리
		if (input[i]-48 != 0)
		{
			dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
			dp[i][0] %= MOD;
		}
		else
		{
			dp[i][0] = 0;
		}
	}
	cout << (dp[size][0] + dp[size][1])%MOD;
	return 0;
}

---

6. 후기

이제 2차원 DP도 뭔가 감을 잡는 듯한 느낌?..