10844. 쉬운 계단 수



문제

45656이란 수를 보자.

이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다.

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1 

1

예제 출력 1 

9

예제 입력 2 

2

예제 출력 2 

17



1. 접근


인접한 모든 자리수의 차이가 1인 수를 계단 수라고 한다.


자리수가 주어질 때, 가능한 계단 수는 몇개나 되는가??



직관적인 다이나믹 프로그래밍이 가능하겠다.


작은 계단 수에서 큰 계단 수를 만들거나, 큰 계단 수에서 작은 계단 수를 만들 수도 있다.




2-1) 탑-다운 풀이


길이가 n인 계단 수는 어떤 수에서 비롯되었을까?


예를 들어 끝이 4라면, 이 계단 수는 끝이 3이거나 5인 계단 수로 만들 수 있다. (3 ->34 or 5 -> 54)



따라서


func(n,x) = 자리수가 n이고 끝이 x인 계단 수의 총 갯수 라고 정의 한다면 다음과 같다.


func(n, x) = func(n-1,x-1) + func(n-1,x+1)


끝의 예외 케이스를 정리해주면 쉽게 재귀적으로 구현 할 수 있다.



2-2) 바텀-업 풀이


길이가 n인 계단 수로 길이가 n+1인 계단 수를 몇개나 만들 수 있을까?


끝이 0이나 9가 아닌 이상 2개나 만들 수 있음은 자명하다.



그러면 이중 포문을 통해, 길이가 가장 작은 경우에서 끝 자리의 10가지 경우를 기록하고, 


이를 토대로 길이를 1늘려서 다시 확인하는 코드가 떠오를 것이다.


dp[d][x] = dp[d-1][x-1] + dp[d-1][x+1]


그게 맞당!




3-1) 코드 1


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <stdio.h>
#include <string.h>
using namespace std;
 
#define MOD 1000000000
 
int n, ans;
int dp[101][10];
 
int func(int d, int x) {
    if (d == 1)
        return x == 0 ? 0 : 1;
 
    int& ref = dp[d][x];
    if (ref != -1)
        return ref;
 
    if (x == 0)
        return ref = func(d - 11) % MOD;
    if (x == 9)
        return ref = func(d - 18) % MOD;
    else
        return ref = (func(d - 1, x - 1+ func(d - 1, x + 1)) % MOD;
}
 
int main() {
    scanf("%d"&n);
 
    memset(dp, -1sizeof(dp));
 
    for (int i = 0; i <= 9++i)
        ans = (ans + func(n, i)) % MOD;
 
    printf("%d", ans);
 
    return 0;
}
cs



3-2) 코드 2


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>
 
#define MOD 1000000000
 
int dp[101][10];
int n, ans = 0;
 
int main(void) {
    scanf("%d"&n);
 
    for (int i = 1; i < 10; i++)
        dp[1][i] = 1;
 
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < 10; j++) {
            if (j == 0)
                dp[i][0= dp[i - 1][1] % MOD;
            else if (j == 9)
                dp[i][9= dp[i - 1][8] % MOD;
            else
                dp[i][j] = (dp[i - 1][j - 1+ dp[i - 1][j + 1]) % MOD;
        }
    }
 
    for (int i = 0; i < 10; i++)
        ans = (ans + dp[n][i]) % MOD;
 
    printf("%d\n", ans);
    return 0;
}
cs


'알고리즘 > Dynamic Programming 동적계획법' 카테고리의 다른 글

백준) 1102 발전소  (0) 2017.09.05
백준) 1562 계단  (0) 2017.09.04
백준) 11049 행렬 곱셈 순서  (0) 2017.08.25
백준) 9520 NP-hard (PUTNIK)  (0) 2017.08.24
백준) 10835 카드게임  (2) 2017.08.24

+ Recent posts