[백준-1562] 계단 수

DP 에 비트마스킹까지 포함시킨 문제이다.

일단 수를 일일이 다 확인해가면서 0부터 9까지 있는지 확인하는 작업은 복잡도 측면에서 몇십배 정도 더 늘어나게 된다. 때문에 이를 위해 비트마스킹 기법을 통한 체킹 로직이 필요하다.

추가로 DP 메모라이징 기법을 통해 이 문제를 비교적 간단하게 풀 수 있다. 처음에만 봤을 때 어렵지 한 번 이해하면 다음에는 쉽지(??!) 않을까 생각하는 문제이다.

다음에 한 번 더 풀어보는 걸로..

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <queue>
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;
typedef pair<int, string> pii;
typedef long long LL;

int N;
int check[10][101][1 << 10];

int stair(int start, int length, int number) {
    if (length == N) 
        return (number == (1 << 10) - 1) ? 1 : 0;
    
    int &result = check[start][length][number];
    if (result != -1)
        return result;

    result = 0;
    if (start - 1 >= 0)
        result += stair(start - 1, length + 1, number | 1 << (start - 1));
    if (start + 1 < 10)
        result += stair(start + 1, length + 1, number | 1 << (start + 1));
    result %= 1000000000;
    return result;
}
int main() {
    cin >> N;

    int res = 0;
    for (int i = 1; i <= 9; i++) {
        memset(check, -1, sizeof(check));
        res += stair(i, 1, 1 << i);
        res %= 1000000000;
    }
    cout << res << endl;

    
    return 0;
}

 

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

1562번: 계단 수