[백준 10844번] 쉬운 계단 수 C++

www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

진짜 동적계획법 하나도 혼자 힘으로 못 풀었는데

이제 혼자 힘으로 쉬운건 풀리기 시작하니 너무 공부할맛 난다

탑다운으로 먼저 풀고 바텀업으로 품

 

dp[x][y] = x번째에 y숫자를 썼을때 횟수 메모이제이션 

이렇게 품 탑다운이랑 바텀업 전부 푼 알고리즘은 똑같음

 

 

탑다운

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
int n;
//현재위치에서 num을 썼을때 나오는 횟수
int dp[101][11];
 
//x=현재위치 y=지금 쓴 수
int stair(int x, int y) {
 
    if (x == n) return 1;
 
    int& ret = dp[x][y];
 
    if (ret != -1) return ret;
 
    if (y == 0) return ret = stair(x + 1, 1) % 1000000000;
    if (y == 9) return ret = stair(x + 1, 8) % 1000000000;
    return ret = (stair(x + 1, y - 1) + stair(x + 1, y + 1)) % 1000000000;
 
}
int main() {
 
    cin >> n;
    memset(dp, -1, sizeof(dp));
    int cnt = 0;
 
    for (int i = 1; i <= 9; i++)
        cnt = (cnt + stair(1, i)) % 1000000000;
 
    cout << cnt;
 
    return 0;
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
 
//현재위치에서 num을 썼을때 나오는 횟수
int dp[101][11];
 
int main() {
 
    memset(dp, -1, sizeof(dp));
 
    int n;
    int cnt = 0;
    cin >> n;
 
    for (int i = 1; i <= 9; i++)
        dp[1][i] = 1;
 
    dp[1][0] = 0;
 
    for (int i = 2; i <= n; i++)
        for (int j = 0; j <= 9; j++) {
            if (j == 0) dp[i][j] = dp[i - 1][j + 1] % 1000000000;
            else if (j == 9)dp[i][j] = dp[i - 1][j - 1] % 1000000000;
            else dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000;
        }
 
    for (int i = 0; i < 10; i++)
        cnt = (cnt + dp[n][i]) % 1000000000;
 
    cout << cnt;
 
    return 0;
}