백준 1562번 계단 수

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

계단수의 대한 개념은 http://jaimemin.tistory.com/359?category=988050(쉬운 계단수)를 통해 익혀놓았기 때문에 쉽게 접근할 수 있었던 문제였습니다.

하지만 이 문제에서는 10844번과 다르게 0~9 모두 등장해야 계단수라고 여깁니다.

처음에 문제를 풀었을 때는 접근 방법은 맞았지만 메모이제이션 시 0~9가 사용되었는지 표기하는 배열을 고려안해서 틀렸습니다.

아래는 제가 처음에 작성한 코드입니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100 + 1;

const int MOD = 1000000000;

 

int N;

int number[10]; //0~9 다 있는지 확인

int cache[10][MAX]; //시작하는 수, 자리수 길이

 

int stairNum(int start, int length, int number[])

{

        //기저 사례 : 숫자 범위

        if (start < 0 || start>9)

                 return 0;

        //기저 사례 : 길이

        if (length > N)

                 return 0;

 

        number[start] = 1; //해당 digit 표시

 

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

        if (result != -1)

                 return result;

 

        int allDigit = 1;

        //0~9 전부 있어야 센다

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

                 if (number[i] == 0)

                 {

                         allDigit = 0;

                         break;

                 }

 

        //계단 수 : 하나씩 차이

        result = allDigit + (stairNum(start - 1, length + 1, number) + stairNum(start + 1, length + 1, number)) % MOD;

 

        number[start] = 0; //해당 digit 다시 없었던걸로

 

        return result;

}

 

int main(void)

{

        cin >> N;

 

        int result = 0;

 

        for(int start = 1; start <= 9; start++)

        {

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

                 memset(number, 0, sizeof(number));

                 result += stairNum(start, 1, number); //0으로 시작할 수 없음

                 result %= MOD;

        }

 

        cout << result << endl;

 

        return 0;

}

앞서 언급했다싶이 0~9가 등장했는지 여부를 판별하는 배열 number를 메모이제이션시 고려하지 않았기 때문에 틀렸습니다.

하지만 주어진 테스트 케이스의 경우에는 잘 작동했기 때문에 낚였습니다...

배열을 고려해야한다는 점을 깨달았지만 앞서 작성한대로 배열을 int number[10];으로 선언할 경우 메모이제이션할 수가 없습니다.

따라서 아래와 같이 bit를 이용하여 배열을 표현해야합니다.

int number=1 << 10;

즉, 십진수가 아닌 이진수를 활용해야합니다. (2^N의 자릿수는 N을 표현)

아래는 AC 받은 코드입니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100 + 1;

const int MOD = 1000000000;

 

int N;

//2진수로 0~9까지 표시

int cache[10][MAX][1 << 10]; //시작하는 수, 자리수 길이, 한자리 숫자 배열(앞서 잘못 생각한 number 역할)

 

int stairNum(int start, int length, int number)

{

        //기저 사례 : 목표 길이 도달

        //0~9 모두 등장했으면 추가

        if (length == N)

                 return number == (1 << 10) - 1 ? 1 : 0;

 

        //메모이제이션 시 number도 고려했어야했다. (전 소스와 다른 점)

        int &result = cache[start][length][number];

        if (result != -1)

                 return result;

 

        result = 0;

        //계단 수 : 하나씩 차이

        if(start - 1 >= 0)

                 result += stairNum(start - 1, length + 1, number | 1 << (start - 1));

        if(start + 1 < 10)

                 result += stairNum(start + 1, length + 1, number | 1 << (start + 1));

       

        result %= MOD;

 

        return result;

}

 

int main(void)

{

        cin >> N;

 

        int result = 0;

 

        for (int start = 1; start <= 9; start++)

        {

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

                 result += stairNum(start, 1, 1 << start); //0으로 시작할 수 없음

                 result %= MOD;

        }

 

        cout << result << endl;

 

        return 0;

}

개발환경:Visual Studio 2017

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

*bit는 TSP(http://jaimemin.tistory.com/365) 알고리즘과 같이 복잡한 알고리즘을 풀 때 자주 쓰이기 때문에 앞으로는 bit 관련 문제를 자주 풀어봐야겠습니다.