✅ dp ✅ Bottom up

문제

링크

풀이

1. 문제 접근 및 해결 로직 (풀이법)

$i$ 번째에 올 수 있는 수는 $i-1$

$i-1$

$i=0$

따라서 점화식을 세워야 한다.

• 정의
  $f(n,d)$ 길이가 n,마지막 숫자가 d인 계단수 개수
• 구하는 답
  $f(n,0)+f(n,1)+f(n,2)+...+f(n,9)$
• 초기값
  $f(1,1)=f(1,2)=f(1,3)=...=f(1,9)=1$
• 점화식
  $f(n,d)=f(n-1,d+1),(d==0)$

• 초기값
  한자리 수일 때는 계단수가 한가지(본인)밖에 없다.
• 점화식
  $i$ 번째 수가 정해지면 $i-1$

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>

using namespace std;

int stair[101][10]; // stair[n][d] : 길이가 n(최대100),마지막 숫자가 d(0~9)인 계단수 개수

int main()
{
    int N, ans = 0;
    cin >> N;

    // 초기값 저장
    stair[1][0] = 0; // 0으로 시작하는 수는 계단수가 아니다.
    for (int i = 1; i <= 9; i++) // 한자리 수일 때는 계단수가 한가지(본인)밖에 없다.
    {
        stair[1][i] = 1;
    }

    for (int n = 2; n <= N; n++)
    {
        for (int d = 0; d <= 9; d++)
        {
            if (d == 0)
                stair[n][d] = stair[n - 1][d + 1] % 1000000000;
            else if (d == 9)
                stair[n][d] = stair[n - 1][d - 1] % 1000000000;
            else
                stair[n][d] = (stair[n - 1][d - 1] + stair[n - 1][d + 1]) % 1000000000;
        }
    }

    for (int d = 0; d <= 9; d++)
    {
        ans  = (ans + stair[N][d]) % 1000000000;
    }

    cout << ans % 1000000000 << "\n";

    return 0;
}

🔥 오버플로우

for (int d = 0; d <= 9; d++)
{
    ans += (stair[N][d] % 1000000000);
}

ans에 stair을 1000000000으로 나눈 나머지들을 더해주면 반복문으로 인해 더해지다가 1000000000을 넘을 수도 있다.(오버플로우)

따라서 ans 자체를 ans+stair을 1000000000으로 나눈 나머지로 바꿔준다.

for (int d = 0; d <= 9; d++)
{
	ans  = (ans + stair[N][d]) % 1000000000;
}

참고로 아에 범위가 큰 long long을 쓰는 것도 방법 중에 하나이다.

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항