[Python] 백준/BOJ 10844번: 쉬운 계단 수 (Silver 1)

💻 Problem

문제 보러 가기

 

45656이란 수를 보자.

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

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

 

💡 Approach

이게 실버 문제라니! DP 너무 어려웡ㅠ

처음 접근할 때는 수의 첫 번째 자리를 기준으로 생각했다.

맨 처음에는 9개의 숫자가 올 수 있고.. 그다음 자리는 2개의 숫자가 올 수 있고..

0이나 9일 때를 고려해야 하고.. 너무....복잡햇.........

 

이 글을 보고 이해할 수 있었다.

음음.. 가장 끝 자리에 오는 숫자를 기준으로 했어야 하는 거구나

 

i는 자릿수이고 j는 끝자리 숫자이다.

예를 들어, i=2, j=4, dp[2][4]=2이면 두 자릿수 숫자 중에 4로 끝나는 숫자가 2개(34, 54)라는 것이다.

끝자리가 0인 경우 0보다 작은 숫자가 없고, 끝자리가 9인 경우 9보다 큰 숫자가 없기에 중간 숫자들과 개수가 다르다.

끝자리가 0이나 9이면 파란색처럼, 끝자리가 1 ~ 8이면 빨간색처럼 하게 된다.

 

참고로 1 ~ 100 모든 정답은 여기서 확인할 수 있다.

 

✏️ Solution

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):
    dp[i][0] = dp[i - 1][1]
    dp[i][9] = dp[i - 1][8]

    for j in range(1, 9):
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

print(sum(dp[N]) % 1_000_000_000)

• 시간복잡도: O(N)