티스토리 뷰

알고리즘 관련/BOJ

BOJ)1562 계단 수

JASON 자손9319 2017. 2. 6. 22:04

문제: icpc.me/1562


N자리 계단수의 개수를 구하는 문제이다.


단 조건이 추가됬는데 0~9까지 모든 수가 등장했는지 확인을 해줘야 하기 때문에 비트마스킹을 통하여 상태를 체크해주면 된다.


dp테이블의 정의는 dp[pos][val][state] 일때 pos자리 수이고 val번째 수로 시작하는 state(켜진 비트에 따라 i번째 자리수가 사용됬는지)의 경우의 수이다.


점화식은 dp[pos][val][state]=dp[pos-1][val+1][state|(1<<val)]+dp[pos-1][val-1][state|(1<<val)]이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MOD 1000000000
using namespace std;
typedef long long ll;
ll dp[110][11][<< 11], n, r;
ll func(ll pos, ll val, ll state) {
    if (val < || val > 9)
        return 0;
    if (pos == 1) {
        if ((state | (<< val)) == ((<< 10- 1))
            return 1;
        else
            return 0;
    }
    ll &ret = dp[pos][val][state];
    if (ret != -1)return ret;
    state |= (<< val);
    return ret = (func(pos - 1, val + 1, state) + func(pos - 1, val - 1, state)) % MOD;
}
int main() {
    scanf("%lld"&n);
    memset(dp, -1sizeof(dp));
    for (ll i = 1; i < 10; i++)
        r = (r + func(n, i, 0)) % MOD;
    printf("%lld", r);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)1893 시저 암호  (0) 2017.02.06
BOJ)9934 완전 이진 트리  (0) 2017.02.06
BOJ)1562 계단 수  (0) 2017.02.06
BOJ)14433 한조 대기 중  (0) 2017.02.06
BOJ)14431 소수마을  (0) 2017.02.06
BOJ) 10282 Failing Components  (0) 2017.02.04
댓글
댓글쓰기 폼