ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 백준 #10844 - 쉬운 계단 수
    알고리즘 2024. 4. 7. 02:07

     

     

    문제

    45656이란 수를 보자.

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

    N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

    입력

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

    출력

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

    예제 입력 1

    1
    

    예제 출력 1

    9
    

    예제 입력 2

    2
    

    예제 출력 2

    17

     

     

     


     

     

    전형적인 dp 문제였다.

    먼저, dp 테이블을 만들어 주었다.

     

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

     

     

    가로는 계단수를 구성할 0~9의 숫자를 나타내고,

    세로는 계단수의 길이를 나타낸다.

     

    계단수의 길이가 0인 경우는 없으니 건너뛰고, 계단수의 길이가 1인 경우부터 보자.

    계단수의 길이가 1일 때는, 0을 제외한 1~9의 경우 모두 1개씩 존재하므로 dp[1]을 [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]로 초기화 한다.

     

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

     

     

    계단수의 길이가 2일 때를 생각해보자.

     

    1) 만일 마지막 숫자가 0이라면, 그 전 숫자는 1만 올 수 있다.

    2) 만일 마지막 숫자가 9라면, 그 전 숫자는 8만 올 수 있다.

    3) 만일 마지막 숫자가 1~8이라면, 그 전 숫자는 (마지막 숫자 - 1), (마지막 숫자 + 1)의 2개이다.

     

    이를 점화식으로 표현해보자.

     

    1) 만일 마지막 숫자가 0이라면 --> dp[i][j] = dp[i - 1][1]

    2) 만일 마지막 숫자가 9라면 --> dp[i][j] = dp[i - 1][8]

    3) 만일 마지막 숫자가 1~8이라면 --> dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

     

    그럼 다음과 같은 식을 작성할 수 있다.

    dp[1]은 초기화 한 상태이기에 i = 2부터 돌면 된다

     

    # 1 2 3 4 5 6 7 8 9
    import sys
    input = sys.stdin.readline
    
    n = int(input())
    dp = [[0] * 10 for _ in range(n + 1)]
    
    dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
    
    for i in range(2, n + 1):
        for j in range(10):
            if j == 0:
                dp[i][j] = dp[i - 1][1]
            elif j == 9:
                dp[i][j] = dp[i - 1][8]
            else:
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
    
    answer = sum(dp[n])
    print(answer % 1000000000)

     

     

    '알고리즘' 카테고리의 다른 글

    백준 #4948 - 베르트랑 공준  (0) 2024.04.08
    백준 #2293 - 동전1  (0) 2024.04.07
    백준 #2240 - 자두나무  (0) 2024.04.02
    백준 #11478 - 서로 다른 부분 문자열의 개수  (0) 2024.04.01
    백준 #11729 - 하노이 탑  (0) 2024.04.01
Designed by Tistory.