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

문제링크 : https://www.acmicpc.net/problem/2780

2780번: 비밀번호

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int T, N, dp[1001][10]; //가능한 숫자, 비밀번호 길이
const int MOD = 1234567;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> T;

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

    for(int i=2; i<=1000; i++) //길이
    {
        for(int j=0; j<10; j++) //숫자
        {
            if(j==0) dp[i][j] = dp[i-1][7]; //인접숫자 체크
            else if(j==1) dp[i][j] = dp[i-1][2] + dp[i-1][4];
            else if(j==2) dp[i][j] = dp[i-1][1] + dp[i-1][3] + dp[i-1][5];
            else if(j==3) dp[i][j] = dp[i-1][2] + dp[i-1][6];
            else if(j==4) dp[i][j] = dp[i-1][1] + dp[i-1][5] + dp[i-1][7];
            else if(j==5) dp[i][j] = dp[i-1][2] + dp[i-1][4] + dp[i-1][6] + dp[i-1][8];
            else if(j==6) dp[i][j] = dp[i-1][3] + dp[i-1][5] + dp[i-1][9];
            else if(j==7) dp[i][j] = dp[i-1][0] + dp[i-1][4] + dp[i-1][8];
            else if(j==8) dp[i][j] = dp[i-1][5] + dp[i-1][7] + dp[i-1][9];
            else if(j==9) dp[i][j] = dp[i-1][6] + dp[i-1][8];

            dp[i][j] %= MOD;
        }
    }

    while(T--)
    {
        int result = 0;
        cin >> N;
        for(int i=0; i<10; i++)
        {
            result += dp[N][i];
        }
        cout << result%MOD << "\n";
    }

    return 0;
}

 

가능한 숫자와 현재 길이를 고려하여 dp 배열을 잡는다.

먼저 길이가 1인 경우는 어떤 숫자든 간에 올 수 있는 경우가 1개 뿐이므로 해당 경우에 대해 1로 초기화 해주고 시작한다.

 

이후에는 현재 숫자 기준으로 인접한 부분의 숫자를 전부 체크하여 더해준다.

0의 경우는 7

1의 경우는 2, 4

2의 경우는 1, 3, 5

3의 경우는 2, 6

4의 경우는 1, 5, 7

5의 경우는 2, 4, 6, 8

6의 경우는 3, 5, 9

7의 경우는 0, 4, 8

8의 경우는 5, 7, 9

9의 경우는 6, 8이다.

 

이를 이용하여 직전 해당 숫자를 참고해 현재 dp 식을 갱신해준다.

이후 문제에 주어진 조건에 따라 1234567을 나눠준다.

 

우리가 구하고자하는 것은 N길이의 경우이기 때문에 매 테스트 케이스마다 반복문을 돌려 해당 길이 N일때 숫자 0~9만큼 확인하여 결과값에 더해준다.

마찬가지로 결과값에 1234567을 나눠주고 출력해주면 된다.