[백준] 10844 : 쉬운 계단 수 / python

1. 문제 설명

10844번: 쉬운 계단 수

45656이란 수를 보자.

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

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

 

입력

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

 

출력

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

 

2. 풀이 전 계획과 생각

• N → 자리수 (1 ~100)

규칙을 찾아보자.

N = 1 ⇒ 1, 2, 3, 4, 5, 6 ......

N = 2 ⇒ 10, 12, 21, 23, 32, 34, 43, 45 ......

N은 N - 1일 때 수에서 +-1 을 1의 자리에 붙는다.

t를 N-1의 0과 9의 갯수라고 할 때,
dp[n] = (dp[n-1] - t) * 2 + t

t가 규칙을 가지고 있지 않다. 🥲

 

3. 풀이하면서 막혔던 점과 고민

🤔 N은 N - 1일 때 수에서 +-1 을 1의 자리에 붙는다는 규칙을 만족하는 점화식을 어떻게 찾을 수 있을까?

0~9일 때 규칙이 동일하지 않으므로, 마지막 수도 상태값에 넣자. → 2차원 배열로 정의하자.

dp[n][l] = dp[n - 1][l - 1] + dp[n - 1][l + 1]
→ 길이가 N 일 때, 마지막 수가 L일 경우의 계단 수

단, 위의 점화식은 l이 (1 ~ 8) 일 때 성립한다.

왜냐하면 0은 +1을 한 1만 허용되고 9는 -1을 한 8만 적용되기 때문이다.

⇒ 구체적인 점화식

• L = 0
  ⇒ dp[N][L] = dp[N - 1][L + 1]
• L = (1 ~ 8)
  ⇒ dp[N][L] = dp[N - 1][L - 1] + dp[N - 1][L + 1]
• L = 9
  ⇒ dp[N][L] = dp[N - 1][L - 1]

⇒ base

dp[1][1] ... dp[1][9] = 1

 

⇒ 구하고자 하는바

dp[N][0] + ... dp[N][9]

 

4. 풀이

N = int(input())
dp = [ [0] * (10) for _ in range(N + 1) ]

for i in range(1, 10):
    dp[1][i] = 1

for i in range(2, N + 1):
    for j in range(0, 10):
        if j == 0:
            dp[i][j] = dp[i - 1][j + 1]
        elif j == 9:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]

total_sum = 0
for i in range(0, 10):
    total_sum += dp[N][i]

print(total_sum % 1000000000)

 

5. 풀이 후 알게된 개념과 소감

• 이전과 비교할 때, 규칙이 보이지 않으면 상태값을 확장해서 접근해보자.