[ boj : 2780] 비밀번호

www.acmicpc.net/problem/2780

2780번: 비밀번호

문제 : 길이 n 자리의 비밀번호를 만들 수 있습니다. 그러나 항상 인접한 번호만 누를수 있습니다. 이때 n이 주어질때 n자리의 비밀번호를 만들 수 있는 경우의 수를 구하시오

 

해설 : 다이나믹프로그래밍 문제입니다.

현재 '1'이라는 숫자를 눌렀다면 '2','4' 둘 중 하나를 누를 수 있죠. 이를 뒤집어서 생각해 보면 현재 '2'를 누르기 위해선 반드시 그 전에 '1','5','3' 중 하나를 누른 상태여야 된다는 것 입니다.

그러면 점화식을 구성할 수 있겠죠.

 

DP[i][j] = 현재 j 길이의 비밀번호이고 숫자 'i'를 선택했을때 만들 수 있는 비밀번호의 경우의 수

 

그럼 테이블을 채우기 위해선

 

DP[i][j] = sum(DP[0~9][j-1]) 이 되겠죠.

 

그대로 코드로 구현해주면 됩니다.

#include<bits/stdc++.h>

using namespace std;

vector<int> v[10] = {
	{7},
	{2,4},
	{1,3,5},
	{2,6},
	{1,5,7},
	{2,4,6,8},
	{3,5,9},
	{0,4,8},
	{5,7,9},
	{6,8}
};
int dp[10][1001];
const int MOD = 1234567;

void solve();
int go(int x, int y);

int main()
{
	int t;
	cin >> t;
	while (t--)
		solve();
}
void solve()
{
	int n;
	cin >> n;
	memset(dp, -1, sizeof(dp));
	int sum = 0;
	for (int i = 0; i <= 9; i++)
		sum = (sum + go(i, n - 1))%MOD;
	cout << sum << "\n";
}
int go(int x, int y)
{
	if (y <= 0)return 1;
	int& ret = dp[x][y];
	if (ret != -1)return ret;

	ret = 0;
	for (int u : v[x])
		ret = (ret + go(u, y - 1)) % MOD;
	return ret;
}