백준18015 어려운 계단 수

작성일 | In

문제 링크

  • http://icpc.me/18015

사용 알고리즘

  • DP

시간복잡도

  • O(NB)

풀이

dp[idx][num][x][y] = idx번째 숫자가 num이고, idx번째까지 0이 나온적이 있는지의 여부가 x, B가 나온적이 있는지의 여부가 y라고 할 때의 정답
으로 정의를 하고 dp를 잘 해주면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef int ll;

ll dp[2020][2020][2][2];
int n, b;
const ll mod = 1e9;

ll f(int idx, int now, int i, int j){
    ll &res = dp[idx][now][i][j];
    if(res != -1) return res;
    if(idx == n) return res = (i && j);
    res = 0;
    if(now > 0) res = (res + f(idx+1, now-1, i | (now == 1), j)) % mod;
    if(now < b-1) res = (res + f(idx+1, now+1, i, j | (now == b-2))) % mod;
    return res;
}

int main(){
    cin >> n >> b;
    memset(dp, -1, sizeof dp);
    int ans = 0;
    for(int i=1; i<b; i++){
        ans = (ans + f(1, i, 0, i == b-1)) % mod;
    }
    cout << ans;
}