[C++] 백준 1562 계단 수

 

#include <iostream>
 
int DP[10][101][1024] = {};
int N = 0;
 
int DFS(int num, int digit, int bit) 
{
    if (DP[num][digit][bit])
    {
        return DP[num][digit][bit];
    }
 
    if (digit == N) 
    {
        if (bit == 1023)
            return 1;
 
        else return 0;
    }
 
    int tmp = 0;
    int next = 0;
 
    if (num < 9) 
    {
        next = num + 1;
        tmp += DFS(next, digit + 1, (bit | 1 << (next)));
    }
 
    if (num > 0) 
    {
        next = num - 1;
        tmp += DFS(next, digit + 1, (bit | 1 << (next)));
    }
 
    tmp %= (int)10e8;
    DP[num][digit][bit] = tmp;
 
    return  DP[num][digit][bit];
}
 
int main() 
{
    std::cin >> N;
 
    int ans = 0;
 
    for (int i = 1; i <= 9; i++) 
    {
        ans += DFS(i, 1, 1 << i);
        ans %= (int)10e8;
    }
 
    std::cout << ans;
 
    return 0;
}

 

 

비트를 이용해서 문제를 풀어야했습니다.

처음엔 방법조차 몰랐는데 비트를 이용해서 문제를 풀었습니다.

DFS처럼 1 -> 2 -> 1or3 이런 방식으로 들어가면서 1을 입력했으면 1 << 1, 2는 1 << 2 이렇게 10개를 확인했어야 합니다.