백준 10844 쉬운 계단수 c++

Dynamic Programming을 이용하는 문제이다.
이 문제는 1차원 배열로는 해결하기가 어렵고 2차원 배열을 이용해야 한다.

테이블 정의

d[i][j] = i길이의 j로 시작하는 수의 계단 수의 합라고 정의했지만 계산하기가 애매했다.
그래서 d[i][j] = i 길이의 j로 끝나는 수의 계단 수의 합으로 정의하니 해결되었다.

점화식 찾기

j가 0일 때와 9일 때 예외처리만 해주면 된다.

if(j==0) d[i][j] = d[i-1][j+1];
else if(j==9) d[i][j] = d[i-1][j-1];
else d[i][j] = d[i-1][j-1]+d[i-1][j+1]

초기값 정의

1부터 9일 때까지 모두 1을 초기값으로 정의해준다.

코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll d[102][10];
ll mod = 1000000000;

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;

    for(int i = 1; i <= 9; i++) {
        d[1][i] = 1;
    }
    d[1][0] = 0;
    for(int i = 2; i <= n; i++) {
        for(int j = 0; j <= 9; j++) {
            if(j == 0) d[i][j] = d[i-1][j+1]%mod;
            else if(j == 9) d[i][j] = d[i-1][j-1]%mod;
            else d[i][j] = d[i-1][j-1]+d[i-1][j+1]%mod;
        }
    }
    
    ll sum = 0;
    for(int i = 0; i <= 9; i++) {
        sum += d[n][i];
    }
    cout << sum%mod;
}

후기

dp를 풀면서 처음으로 2차원배열을 적용시켜봤다.
처음에 조금 난감했지만 할만했다.