[백준 c++] 10844 쉬운 계단 수

문제

https://www.acmicpc.net/problem/10844
인접한 모든 자리의 차이가 1인 N자리 수가 몇 개인지 구하는 문제다.
ex) 45654, 101

풀이

top-down 방식의 dp로 풀었다.
1.맨 처음 올 수 있는 수는 1~9 이므로 for문으로 함수 go(1,i)를 호출한다.

• go(int lv, int k)에서 lv은 트리의 깊이, k는 다음 자리에 입력된 수다.
  
  

2.함수 내에 k와 lv의 범위를 설정해준다.

• k는 9보다 크거나 0보다 작으면 0을 return한다.
• lv == n이 되면 트리의 맨 아래까지 온 것이므로 1을 return한다.
  
  

3.dp[lv][k] += go(lv + 1, k - 1) + go(lv + 1, k + 1)

• 1차이가 나려면 1을 더하거나 빼는 경우다.
  
  

아무리 생각해도 bottom-up방식보다 top-down이 쉬운건 뭘까..

코드

#include <iostream>
#include <algorithm>
using namespace std;
long long n, dp[101][10], ret;
static long mod = 1000000000;

long long go(int lv, int k)
{
    if (k > 9 || k < 0)
        return 0;

    if (lv == n)
        return 1;

    if (dp[lv][k])
        return dp[lv][k];

    dp[lv][k] += go(lv + 1, k - 1) + go(lv + 1, k + 1);

    return dp[lv][k] % mod;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= 9; i++)
        ret += go(1, i);
    cout << ret % mod << "\n";
}