[BOJ/백준][Gold1] 1562 : 계단 수 (C++)

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

1562번: 계단 수

 

 

[유형] DP

[풀이]
bitmask를 이용한 3차원 dp를 이용해 해결이 가능합니다.

dp[n][m][bit] : 맨 앞자리수가 m이면서, 길이가 n이고, bit에 mask된 숫자들을 사용한 숫자들의 개수

 

#include <cstdio>
#include <cstring>
using namespace std;
int N,dp[101][10][1<<10],mod=1e9;
int sol(int n,int m,int bit){
    if(n==N) return ((1<<m)|bit)==((1<<10)-1);

    int& ret = dp[n][m][bit];
    if(ret!=-1) return ret;
    ret=0;
    bit |= (1<<m);
    if(m-1>=0) ret=(ret+sol(n+1,m-1,bit))%mod;
    if(m+1<10) ret=(ret+sol(n+1,m+1,bit))%mod;
    return ret;
}
int main(){
    scanf("%d",&N);
    memset(dp,-1,sizeof(dp));
    int ans=0;
    for(int i=1;i<10;i++){
        ans+=sol(1,i,0);
        ans%=mod;
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold1/1562.cpp