[백준 2780번] 비밀번호 (C++ / c++)

 

 

 

백준 2780번

 

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

2780번: 비밀번호

 

---

백준 2780번
비밀번호

---

이 문제는 DP 유형 중 하나입니다!
다른 방법도 있겠지만, 저는 그렇게 이해했어요!

문제를 살펴보면 "비밀번호에서 인접한 수는 실제 위 기계의 번호에서도 인접해야 한다." 라는 부분이 있습니다.
이 말을 곰곰히 곱씹어 보면, 숫자 하나당 연결될 수 있는 비밀번호가 고정되어 있다는 것을 알 수 있어요.

 

예시를 들어보자면
1 다음에는 2와 4가 올 수 있고, 
2 다음에는 1, 3, 5가 올 수 있습니다.
5 다음에는 2, 4, 6, 8이 올 수 있고요!

 

반대로 생각해보면

1 앞에는 2와 4가 올 수 있고, 
2 앞에는 1, 3, 5가 올 수 있습니다.
5 앞에는 2, 4, 6, 8이 올 수 있고요!

 

비밀번호의 길이를 N이라고 해봅시다.

이 비밀번호의 N번째에 가능한 숫자들은 N-1번째 자리의 숫자가 N번째 자리 숫자와 인접할 수 있는 경우 뿐입니다.

 

이걸 수식으로 바꾸면
DP[N][y] = Dp[N-1][x1] + Dp[N-1][x2]....

(단 x1,2..는 y와 인접할 수 있는 수이다.)
(+ y는 N번째 자리수)

N이 1일 때는 한자리수 비밀번호라는 뜻이니, 각 DP[1][y]는 1밖에 안되겠죠?

이를 코드로 구현하면 아래와 같습니다.

 

#include <iostream>
using namespace std;

int dp[1001][10];
int main()
{
	int T;
	int res;
	int input;

	cin >> T;
	
	for(int i = 0; i < 10; i++)
	{
		dp [1][i] = 1;
	}
	for(int i = 2; i <= 1000; i++ )
	{
		for(int k = 0; k < 10; k++)
		{
			switch(k)
			{
				case 0 : 
					dp[i][k] = dp[i-1][7];
					break;
				case 1 : 
					dp[i][k] = dp[i-1][2] + dp[i-1][4];
					break;
				case 2 : 
					dp[i][k] = dp[i-1][1] + dp[i-1][3] + dp[i-1][5];
					break;
				case 3 : 
					dp[i][k] = dp[i-1][2] + dp[i-1][6];
					break;
				case 4 : 
					dp[i][k] = dp[i-1][1] + dp[i-1][5] + dp[i-1][7];
					break;
				case 5 : 
					dp[i][k] = dp[i-1][2] + dp[i-1][4] + dp[i-1][6] + dp[i-1][8];
					break;
				case 6 : 
					dp[i][k] = dp[i-1][3] + dp[i-1][5] + dp[i-1][9];
					break;
				case 7 : 
					dp[i][k] = dp[i-1][0] + dp[i-1][4] + dp[i-1][8];
					break;
				case 8 : 
					dp[i][k] = dp[i-1][5] + dp[i-1][7] + dp[i-1][9];
					break;
				case 9 : 
					dp[i][k] = dp[i-1][6] + dp[i-1][8];
					break;
				}
			dp[i][k] = dp[i][k] % 1234567;
		}
	}
	while(T--)
	{
		res = 0;
		cin >> input;
		for(int i = 0; i < 10; i++)
		{
			res = (res + dp[input][i]) % 1234567;
		}
		cout << res % 1234567 << '\n';
	}
	return 0;
}