BOJ 1562 계단 수

문제 링크 : https://www.acmicpc.net/problem/1562

1562번: 계단 수

 

집합을 표현하거나 본 문제에서처럼 어떤 것들의 사용 여부를 기억할 필요가 있을 때, 비트마스크(bitmask)를 종종 쓴다.

여기서는 0 ~ 9 까지의 사용여부를 bit 로 표현한다.( 중복 사용이 가능하므로 집합과는 다르다. 오른쪽이 하위 bit 이다.)

 

예를 들어,

0 만 사용된 수라면 0000000001 로 0 번 bit 만 1 이 된다. 

1, 4, 9 가 사용되었다면 1000010010 처럼 9번, 4번, 1 번 bit 가 1로 채워진다.

 

부분 문제를 정의하자.

dp[p][x][mask] 는

1. mask 에 1 인 bit 들에 해당되는 수들만 사용해서

2. p 자리까지 채워지고

3. 마지막 수는 x 인 것의 갯수이다. 

 

1.  Bottom-Up

$dp[i][x][mask]$ 를 알고 있다고 하자.

i 번째 수가 x 로 끝나는 경우의 수를 알고 있다는 뜻인데, 이 수 $dp[i][x][mask]$ 는 

$ dp[i+1][x+1][mask | 1 << x+1 ] $ 와 $ dp[i+1][x-1][mask | 1 << x-1 ] $ 에 기여한다.

 

기저 사례들은 $dp[1][i][1<<i]=1 \; (i \ne 0)$ 이다. (첫 수가 0 일 수 없으니...)

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

const ll mmod=1e9;

ll dp[101][10][1<<10];

int main(){
    int n; scanf("%d",&n);
    
    for(int i=1;i<10;i++) dp[1][i][1<<i]=1;
    for(int i=1;i<n;i++){
        for(int x=0;x<10;x++){
            for(int mask=0;mask<1<<10;mask++){
                if(!dp[i][x][mask]) continue;
                if(x<9) {
                    dp[i+1][x+1][mask|1<<x+1]+=dp[i][x][mask];
                    dp[i+1][x+1][mask|1<<x+1]%=mmod;
                }
                
                if(x>0) {
                    dp[i+1][x-1][mask|1<<x-1]+=dp[i][x][mask];
                    dp[i+1][x-1][mask|1<<x-1]%=mmod;
                }
            }
        }
    }
    
    ll ans=0;
    for(int i=0;i<10;i++)
        ans+=dp[n][i][(1<<10)-1], ans%=mmod;
    printf("%lld\n",ans);
}

 

 

이번에는 재귀함수 호출을 이용한 탑다운 코드를 보자.

2.  Top-Down

탑다운 방식으로 진행할 때 위의 코드와 달라진 것은 dp 의 초기값들을 -1 로 둔 것이다.

경우의 수를 다룸에 있어서 불가능한 것을 0 으로 두는 것에 논리적인 문제는 없다.

하지만 부분 문제들이 불가능하지 않지만 0 의 값을 가지는 경우에,

갯수로서 0 인지 아직 부분 문제를 다룬 적이 없다는 뜻의 0 인지 구별할 수 없게 되기 때문이다.

(부분 문제들이 계산되었을 때 반드시 양수를 가진다면 초기값을 0 으로 두어도 문제 없다.)

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

const ll mmod=1e9;

int n;
ll dp[101][10][1<<10];

ll recur(int p,int x,int mask){
    if(p==n) {
        if(mask==(1<<10)-1) return 1;
        else return 0;
    }
    
    ll &ret=dp[p][x][mask];
    if(ret!=-1) return ret;
    
    ret=0;
    if(x<9) ret=recur(p+1,x+1,mask|1<<x+1), ret%=mmod;
    if(x>0) ret+=recur(p+1,x-1,mask|1<<x-1), ret%=mmod;

    return ret;
}

int main(){
    memset(dp, -1, sizeof dp);
    scanf("%d",&n);
    
    ll ans=0;
    for(int i=1;i<10;i++)
        ans+=recur(1,i,1<<i), ans%=mmod;
    
    printf("%lld\n",ans);
}