[백준] 1562번 계단 수 C++

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

1562번: 계단 수

0부터 9 까지 숫자가 모두 등장하는지도 확인해야 된다. 

비트필드를 활용한 dp로 문제를 해결하였다.

 

비트 필드 관련 설명

int arr[1<<10]을 하면 arr[1024]만큼 선언된다.

 

int visited = 3 ---> 이진수로 0011

visited = visted | ( 1 << (3)); 실행시 0011 | 0100 = 0111이 된다.

 

int visited가 11111 11111 인지 확인하기 위해서는

visited == (1<<10)-1 인지 확인하면 된다.

visited == 1023 과 동일.

 

쉬운 계단 수 문제의

stair(길이, 숫자, 각 숫자가 나온지 확인하는 비트필드)로 함수를 작성하여 탑다운 방식으로 해결하였다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include <string>

using namespace std;

int N;
int dp[101][10][1<<10];
int modul = 1000000000;

int stair(int leng,int num,int visited) {
    if (leng == 1) {

        if (visited == 1023) {
            return 1;
        }
        return 0;
        
    }

    if (dp[leng][num][visited] != -1)
        return dp[leng][num][visited];

    if (num == 0)
        return dp[leng][num][visited] = stair(leng - 1, 1, visited | (1 << (num+1)))%modul;
    if (num == 9)
        return dp[leng][num][visited] = stair(leng - 1, 8, visited | (1 << (num-1)))%modul;
    
    return dp[leng][num][visited] =
        (stair(leng - 1, num - 1, visited | (1 << (num-1))) % modul +
         stair(leng - 1, num + 1, visited | (1 << (num+1))) % modul) % modul;
    
}



int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    memset(dp, -1, sizeof(dp));
    cin >> N;

    int visited = 0;
    int val = 0;
    for (int i = 1; i <= 9; i++) {
        val = (val % modul + stair(N, i, 1 << i) % modul) % modul; 
    }

    cout << val;

}