백준[1562] 계단 수

계단 수

문제 링크

http://icpc.me/1562

1562번: 계단 수

풀이

비트마스크 dp문제다.

dp[자릿수][마지막 수][사용한 수]로 정의하면 dp[i][j][k | (1 << j)] += dp[i-1][j-1][k] + dp[i-1][j+1][k]로 정의할 수 있다.

cf) 초기화 하는 부분에서 0부터 초기화하여 시간을 많이 뺏겼다.

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll dp[102][11][1 << 10];
const ll mod = 1e9;

int main() {
    int n; scanf("%d", &n);
    for (int i = 1; i < 10; i++) dp[1][i][1 << i] = 1; // 0으로 시작하면 안되기 때문에 1부터 초기화 시킨다.
    for (int i = 2; i <= n; i++) for (int j = 0; j < 10; j++) for (int bit = 0; bit < (1 << 10); bit++) {
        if (j < 9) dp[i][j][bit | (1 << j)] = (dp[i][j][bit | (1 << j)] + dp[i - 1][j + 1][bit]) % mod;
        if (j > 0) dp[i][j][bit | (1 << j)] = (dp[i][j][bit | (1 << j)] + dp[i - 1][j - 1][bit]) % mod;
    }
    ll ans = 0;
    for (int i = 0; i < 10; i++) ans = (ans + dp[n][i][(1 << 10) - 1]) % mod;
    printf("%lld", ans);
}