백준 BOJ 1562 - 계단 수

비트DP였다.

방문한 적이 있는 숫자들을 비트에 박아넣으면 된다.

 

www.acmicpc.net/problem/1562

1562번: 계단 수

dp[i][j][k] 를

현재 문자열 길이가 i이고, 지금 제일 앞 숫자가 j이고, chk 비트필드가 k일때로 뒀다.

 

#include <bits/stdc++.h>
#define MOD 1000000000
using namespace std;

typedef long long ll;

ll dp[123][12][1<<11];
ll n,ans = 0;

ll f(ll len, ll now, ll bit){
	if(0>now || now>9) return 0;
	
	if(len == n){
		if(bit == (1<<10)-1) return 1;
		else return 0;
	}
	
	if(dp[len][now][bit] != -1) return dp[len][now][bit];
	dp[len][now][bit] = (f(len+1,now+1,bit|(1<<(now+1))) + f(len+1,now-1,bit|(1<<(now-1)))) % MOD;
	return dp[len][now][bit];
}

int main(){
	memset(dp, -1, sizeof(dp));
	scanf("%lld", &n);
	for(int i=1; i<10; i++) ans = (ans + f(1,i,1<<i)) % MOD;
	printf("%lld", ans);
	return 0;
}

적당하게 AC.