[백준] 10844번 쉬운 계단 수(feat. 다이나믹 프로그래밍)

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

 

문제 접근

• 첫 번째 단계 (문제 요약 및 조건 파악)

인접한 모든 자리의 차이가 1인 수를 계단 수라고 한다, (0으로 시작하는 수는 계단수가 아니다)

N이 주어지면, 길이가 N인 계단 수가 총 몇개 있는지 구해야 한다.

N은 1<= N <= 100 인 자연수다.

 

• 두 번째 단계 (문제 핵심 파악하기)

예를 들어 N이 1인 경우를 생각해 보자,

1
2
3
4
5
6
7
8
9

총 9개가 계단수가 된다.
한자리 수는 0을 제외하고는 모두 다 계단수가 될 수 있다.

이번에는 N이 2인 경우를 생각해보자.

10  // 1보다 1작은것
12  // 1보다 1 큰것
21
23
32
34
45
43
54
56
65
67
76
78
87
89
98 -> 9에 대해서는 올 수 있는 것이 1개다

총 17개다.

앞서 살펴본 두 가지 경우를 잘 살펴보면,
맨뒤가 0이면 계단수가 1개만 가능하고,  맨뒤가 9일 때도, 계단수는 1개만 가능하다

그렇다면, 결국, 맨 뒤에 0이 몇 개있고, 1이 몇개 있고... 등 만 알면 된다는 것이다.
즉, 각 숫자에 대하여 몇개씩 있는지가 궁굼한 것이다.

  1 2 3 n...
0 0 1 1
1 1 1 3
2 1 2 3
3 1 2 4
4 1 2 4
5 1 2 4
6 1 2 4
7 1 2 4
8 1 2 3
9 1 1 2

1열의 값을 다 더하면 n이 1일 때의 계단수가 나올 것이고, 이것을 1,000,000,000로 나눈 나머지를 출력하면 n이 1일때의 정답이 된다.
2열의 값을 다 더하면 n이 2일 때의 계단수가 나올 것이고, 이것을 1,000,000,000로 나눈 나머지를 출력하면 n이 2일때의 정답이 된다.

 

 

코드 작성

import sys

def solve():
    n = int(sys.stdin.readline().rstrip())  # n 입력받기

    dp = [[0] * 10 for _ in range(n)]   # 0 ~ 9의 갯수를 n개 저장할 수 있는 dp 테이블 선언 및 초기화

    for i in range(1, 10):  # n이 1 일 때의 계단 수를 저장하기
        dp[0][i] = 1

    for len_n in range(1, n):
        for last_num in range(10):
            if last_num == 0:   # 뒷자리가 0인 경우
                dp[len_n][last_num] = dp[len_n - 1][last_num + 1]   # 예를 들어 n이 2이고 뒷자리가 0이면 계단수로는 10만 가능 9는 불가능
            elif last_num == 9: # 뒷자리가 9인 경우
                dp[len_n][last_num] = dp[len_n - 1][last_num - 1]   # 예를 들어 n이 2이고 뒷자리가 9이면 계단수로는 98만 가능, 100은 불가능
            else:   # 뒷자리가 0과 9가 아닌 경우
                dp[len_n][last_num] = dp[len_n - 1][last_num - 1] + dp[len_n - 1][last_num + 1]

    print(sum(dp[n - 1]) % 1000000000)

solve()