[C++] 백준 2780번: 비밀번호

문제 링크

2780번: 비밀번호

문제 요약

키패드가 주어지고, 비밀번호를 누르는데, 한 버튼을 누르면 그 다음으로는 인접한 버튼만 누를 수 있다. 만들 수 있는 N자리 비밀번호의 수를 구해야 한다.

접근 방법

1. dp[10][1001] 배열을 만들어 두고, dp[0][1]부터 dp[9][1]까지를 모두 1로 초기화 해둡니다.
2. 0부터 9까지 이동하면서, 현재 길이보다 1큰 인덱스에 각 칸의 인접한 칸에 현재 칸의 수를 더해줍니다. 모듈러 연산에 주의해 주어야 합니다.
3. 각 길이에 대해서, dp 배열을 참고해 0 ~ 9까지의 합을 모두 구해둡니다.

코드

#include <bits/stdc++.h>

using namespace std;

const long long MOD = 1234567;
int button[4][3], dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
long long dp[10][1001], sum[1001];
vector<int> adj[10];

void init(void) {
	for (int i = 0; i < 10; i++)
		dp[i][1] = 1;

	int num = 1;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			button[i][j] = num++;

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 4; k++) {
				int ni = i + dir[k][0], nj = j + dir[k][1];
				if (ni >= 0 && ni < 3 && nj >= 0 && nj < 3)
					adj[button[i][j]].push_back(button[ni][nj]);
			}
		}
	}

	adj[0].push_back(7);
	adj[7].push_back(0);

	for (int i = 2; i <= 1000; i++) {
		for (int j = 0; j < 10; j++) {
			for (auto& k : adj[j]) {
				dp[k][i] += dp[j][i - 1];
				dp[k][i] %= MOD;
			}
		}
	}

	for (int i = 1; i <= 1000; i++) {
		for (int j = 0; j < 10; j++) {
			sum[i] += dp[j][i];
			sum[i] %= MOD;
		}
	}
}

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

	init();

	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;
		cout << sum[n] << '\n';
	}

	return 0;
}