[백준 1562] 계단 수

 

 

문제 : https://www.acmicpc.net/problem/1562

1562번: 계단 수

 

 

쉬운 계단 수 (https://www.acmicpc.net/problem/10844) 문제의 비트 마스크 버전이라고 보면 된다.

 

처음 봤을 때 DP인 것을 눈치채고 또한 0부터 9까지 모든 숫자가 한 번씩은 다 나와야 한다고 하기에 

비트 마스크를 이용하면 되겠구나 생각했다.

 

처음에는 메모이제이션을 위해 생각한 배열은 아래와 같았다.

int memo[len][situation];

여기서 len은 현재 문자열의 길이, situation은 0~9까지 등장한 숫자를 비트로 표현한 비트 마스크이다.

 

그러나 문제가 생겼다. 계단 수 임을 나타낼 수가 없었다.

그래서 2차원에서 3차원으로 배열을 바꿨다.

int memo[len][curNum][situation];

len과 situation은 위의 것과 동일하고 curNum은 현재 len 길이의 문자열에서 가장 마지막 숫자 즉, 제일 오른쪽에 있는 숫자를 말한다. 

 

현재 문자열의 마지막 숫자를 알고 있기 때문에 계단 수 생성을 위해 다음 추가할 숫자는 두 가지 경우 중 하나.

• curNum + 1

• curNum - 1

curNum이 0과 9인 경우는 따로 처리를 해줘야 한다.

 

 

무튼 소스코드는 아래와 같다. 

 

// 계단 수
// https://www.acmicpc.net/problem/1562
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

int n;
int memo[101][10][1<<10];

int solve(int len, int cur, int situ){
    int &ret = memo[len][cur][situ];
    if(ret != -1) return ret;
    
    if(len == n){
        if(situ == (1<<10)-1)
            return 1;
        else
            return 0;
        
    }
    
    ret = 0;
    if(cur == 0){
        ret += solve(len+1, cur+1, situ | (1 << (cur+1)));
        ret %= 1000000000;
    }
    else if(cur == 9){
        ret += solve(len+1, cur-1, situ | (1 << (cur-1)));
        ret %= 1000000000;
    }
    else{
        ret +=solve(len+1, cur-1, situ | (1 << (cur-1)));
        ret %= 1000000000;
        ret += solve(len+1, cur+1, situ | (1 << (cur+1)));
        ret %= 1000000000;
    }
    return ret %= 1000000000;;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    memset(memo, -1, sizeof(memo));
    
    
    int sum = 0;
    for(int i = 1; i < 10; i++){
        int situ = (1 << i);
        sum += solve(1, i, situ);
        sum %= 1000000000;
    }
    
    cout << sum << '\n';
    
    return 0;
}