[BOJ, C++]#10844_쉬운 계단 수, DP, 동적 계획법, 점화식

#1. 문제

https://www.acmicpc.net/problem/10844

 

---

 

#2. 풀이

 

1. DP

[알고리즘]#5_동적 계획법

DP(Dynamic Programming)은 주어진 입력 크기에 따라서 하위 문제를 재귀적으로 해결하는 동시에, 그 결과 값을 기억함으로써 중복 계산을 방지하는 최적화 기법입니다. 

 

2. DP는 점화식을 먼저 세우자!

1. dp [i][j] = dp [i-1][j-1] + dp [i-1][j+1], if j!= 9 && j!= 0 : 현재 위치에 들어갈 j라는 숫자는 직전 위치의 숫자들 중 j-1과 j+1이 들어가는 경우를 모두 더한 결과 값이 됩니다. 이때, j가 9나 0이 아니여야 합니다.
2. dp [i][0] = dp [i-1][1], if j = 0 : 현재 위치에 들어갈 j라는 숫자가 0일 경우, 직전 위치의 숫자가 '1'일 경우만 가능합니다.
3. dp [i][9] = dp [i-1][8], if j = 9 : 현재 위치에 들어갈 j라는 숫자가 9일 경우, 직전 위치 숫자가 '8'일 경우만 가능합니다.
4. 위 점화식을 바탕으로, 코드를 작성해줍니다!

 

---

 

#3. 코드

@@ -0,0 +1,69 @@
/*
    @링크: https://www.acmicpc.net/problem/10844
*   @문제: 쉬운 계단 수
*   @설명
        1. DP
        2. 점화식: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1], if j != 9 && j != 0
                    if j = 0, dp[i][0] = dp[i-1][1], if j = 9, dp[i][9] = dp[i-1][8].
*/


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define MOD 1000000000
typedef long long ll;

int N;
ll dp[101][10];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    //@기저 조건: 한 자리일 경우 1개만 가능 
    for(int i=1; i<=9; ++i)
    {
        dp[1][i] = 1;
    }

    //@N이 2일 경우부터 시작
    for(int i=2; i<=N; ++i)
    {
        for(int j=0; j<=9; ++j)
        {
            //@현재 숫자의 마무리가 0일 경우, 이전 숫자의 마무리가 1일 경우에 한함
            if(j == 0)
            {
                dp[i][j] = dp[i-1][1];
            }
            //@현재 숫자의 마무리가 9일 경우, 이전 숫자의 마무리가 9일 경우에 한함
            else if(j == 9)
            {
                dp[i][j] = dp[i-1][8];
            }
            //@이전 숫자의 마무리가 j-1일 경우 + 마무리가 j+1일 경우
            else
            {
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % MOD;
            }
        }
    }

    //@정답 출력, MOD로 나눈 나머지 값으로 설정해주는 것!
    ll ans = 0;
    for(int j=0; j<=9; ++j)
    {
        ans = (ans+dp[N][j])%MOD;
    }

    cout << ans;

    return 0;
}

 

---