백준 2780번 비밀번호

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

http://jaimemin.tistory.com/359과 유사한 문제였기 때문에 나름 쉽게 풀 수 있었던 문제였습니다. 

다만, 비밀번호의 길이가 늘어나면서 방법의 수가 엄청 늘어나기 때문에 메모이제이션할 때 또한 MOD의 나머지를 더해줘야 AC 처리가 됩니다.

알고리즘은 맞았지만 MOD의 나머지를 더해주지 않아 여러번 틀렸습니다 ㅠㅠ

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MOD = 1234567;

 

int cache[10][1001]; //시작 숫자, 비밀번호 길이

 

//기계의 번호에서 인접한 숫자 표시

int boundary[10][10] = {

        {0, 0, 0, 0, 0, 0, 0, 1, 0, 0}, //0

        {0, 0, 1, 0, 1, 0, 0, 0, 0, 0}, //1

        {0, 1, 0, 1, 0, 1, 0, 0, 0, 0}, //2

        {0, 0, 1, 0, 0, 0, 1, 0, 0, 0}, //3

        {0, 1, 0, 0, 0, 1, 0, 1, 0, 0}, //4

        {0, 0, 1, 0, 1, 0, 1, 0, 1, 0}, //5

        {0, 0, 0, 1, 0, 1, 0, 0, 0, 1}, //6

        {1, 0, 0, 0, 1, 0, 0, 0, 1, 0}, //7

        {0, 0, 0, 0, 0, 1, 0, 1, 0, 1}, //8

        {0, 0, 0, 0, 0, 0, 1, 0, 1, 0} //9

};

 

int password(int digit, int length)

{

        int &result = cache[digit][length];

        if (result != -1)

                 return result;

       

        result = 0;

        for (int i = 0; i < 10; i++)

                 if (boundary[digit][i]) //인접하다면

                         result += (password(i, length - 1) % MOD);

 

        return result;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

       

        for (int i = 0; i < test_case; i++)

        {

                 int N;

                 cin >> N;

 

                 memset(cache, -1, sizeof(cache));

                 for (int i = 0; i < 10; i++)

                         cache[i][1] = 1; //초기값(0~9까지는 1)

 

                 long long sum = 0;

                 for (int i = 0; i <= 9; i++)

                 {

                         sum += password(i, N);

                         sum %= MOD;

                 }

 

                 cout << sum << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~