✅ dp ✅ Bottom up

문제

링크

풀이

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

$i$ 번째에 올 수 있는 수는 $i-1$(바로 직전) 숫자가 무엇인지에 따라 다르다.

$i-1$	$i$
0	1
1	0,2
2	1,3
3	2,4
4	3,5
5	4,6
6	5,7
7	6,8
8	7,9
9	8

$i-1$ 번째 수도 마찬가지로 $i-2$ 번째 수가 뭔지에 따라 다르다.
즉 모든 자리가 그 직전 숫자에 따라 영향을 받는다.

$i=0$ 에서부터 $i=n-1$ 까지 차례대로 이전 수를 확인해가면서 경우의 수를 구할 수도 있지만 그러면 이미 수행했던 과정을 반복하게 되어 시간초과가 나게될 것 이다.
("정답을 1,000,000,000으로 나눈 나머지를 출력한다." 에서 경우의 수가 굉장히 많아 시간초과가 날 것이라는걸 눈치챌 수 있음)

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

• 정의
  $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$
  0으로 시작하는 계단수는 없다고 했으므로 $f(1,0)=0$
• 점화식
  $f(n,d)=f(n-1,d+1),(d==0)$
  $f(n,d)=f(n-1,d-1),(d==9)$
  $f(n,d)=f(n-1,d-1)+f(n-1,d+1),(0<d<9)$

• 초기값
  한자리 수일 때는 계단수가 한가지(본인)밖에 없다.
• 점화식
  $i$ 번째 수가 정해지면 $i-1$(바로 직전) 번째 숫자도 정해진다는 점을 이용해
  위 $i-1$, $i$ 번째 수의 관계표를 보고 점화식을 도출한다.

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(재귀)으로 풀지는 선택사항