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

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

2780번: 비밀번호

문제

석원이는 자신의 현관문에 비밀번호 기계를 설치했다. 그 기계의 모양은 다음과 같다.

지나가던 석원이 친구 주희는 단순한 호기심에 저 비밀번호를 풀고 싶어한다. 이때 주희는 바닥에 떨어져 있는 힌트 종이를 줍게 된다. 이 종이에는 석원이가 비밀번호를 만들 때 사용했던 조건이 적혀 있다. 이제 주희는 이 조건을 가지고, 석원이 집의 가능한 비밀번호의 전체 개수를 알고 싶어 한다. 현재 컴퓨터를 사용할 수 없는 주희는 당신에게 이 문제를 부탁했다. 석원이의 힌트 종이는 다음과 같다.

1. 비밀번호의 길이는 N이다.
2. 비밀번호는 위 그림에 나온 번호들을 눌러서 만든다.
3. 비밀번호에서 인접한 수는 실제 위 기계의 번호에서도 인접해야 한다.

(ex. 15 라는 비밀번호는 불가능하다. (1과 5는 인접하지 않는다. ) 하지만 1236이라는 비밀번호는 가능하다.)

---

 

전형적 DP 문제이다. 비밀번호 길이가 N이기 때문에 N번째 자리에 숫자x가 왔을 때 만들 수 있는 비밀번호 경우의 수를 저장하여 메모이제이션 해주면 된다. 비슷한 유형의 DP문제가 많은 문제라 어렵지 않게 해결할 수 있었던 문제이다.

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <climits>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1234567
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
ll cache[1000 + 1][10 + 1];

bool isValid(int x, int y) {
	if (x == 1) {
		if (y == 2 || y == 4) return true;
		return false;
	}
	else if (x == 2) {
		if (y == 1 || y == 3 || y == 5) return true;
		return false;
	}
	else if (x == 3) {
		if (y == 2 || y == 6) return true;
		return false;
	}
	else if (x == 4) {
		if (y == 1 || y == 5 || y == 7) return true;
		return false;
	}
	else if (x == 5) {
		if (y == 2 || y == 4 || y == 6 || y == 8) return true;
		return false;
	}
	else if (x == 6) {
		if (y == 3 || y == 5 || y == 9) return true;
		return false;
	}
	else if (x == 7) {
		if (y == 4 || y == 8 || y == 0) return true;
		return false;
	}
	else if (x == 8) {
		if (y == 5 || y == 7 || y == 9) return true;
		return false;
	}
	else if (x == 9) {
		if (y == 6 || y == 8) return true;
		return false;
	}
	else {
		if (y == 7) return true;
		return false;
	}
}

ll path(int index, int value) {
	if (index == N) return 1;
	ll& ret = cache[index][value];
	if (ret != -1) return ret;

	ret = 0;
	for (int next = 0; next <= 9; next++) {
		if (!isValid(value, next)) continue;
		ret += path(index + 1, next) % Mod;
	}
	return ret;
}

void input() {
	int testCase;
	cin >> testCase;
	for (int tc = 0; tc < testCase; ++tc) {
		cin >> N;
		memset(cache, -1, sizeof(cache));

		ll answer = 0;
		for (int number = 0; number <= 9; number++) {
			answer += path(1, number);
			answer %= Mod;
		}
		cout << answer << endl;
	}
}

int main() {
	fastio;
	input();
	

	return 0;
}