백준 10844번 쉬운 계단 수 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 10844 쉬운 계단 수

10844 쉬운 계단 수

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

10844번: 쉬운 계단 수

DP 문제로 증가와 감소 상관없이 1씩 계단식으로 이루어진 수의 경우를 구하는 문제로 0은 제일 앞에 올 수 없다. 쉬운 이라는 타이틀이 무색하게 어려웠다.😅

---

소스코드

import sys
input = sys.stdin.readline

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(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]

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

---

풀이

우선 dp[n]에서 n은 자릿수로 0~9까지의 수들이 n번째 자릿수로 들어갈 수 있는 경우의 수를 dp로 저장한다 개념을 알고 시작하는 점이 중요하다. 각 자릿수의 dp들을 활용하여 다음 자릿수의 경우의 수를 구하는 문제이다.

 

0 ~ 9까지 수에서 1씩 증가 혹은 감소하는 수는 0과 9를 제외하면 두 가지씩이다. ex) 1 = 0, 2 / 4 = 3, 5

0일 때는 1만 가능하고 9일 때에는 8만 가능하다.

n = 1일 때 0을 제외한 모든 수가 올 수 있고 이를 1로 표시한다. = 9 (소스코드에서는 for문을 이용해 값을 입력함)

n = 2 일때 0, 1은 한 가지 2~8까지 2가지 경우의 수, 9에서 한 가지이다. = 17 (dp[2] = [1, 1, 2, 2, 2, 2, 2, 2, 2, 1])

이를 토대로 점화식을 만들면 (자릿수 = i, 1~8 = j)

dp[i][0] = dp[i - 1][1],

dp[i][1~8] = dp[i - 1][j - 1] + dp[i - 1][j + 1],

dp[i][9] = dp[i - 1][8]

의 식이 만들어진다.

dp[n]의 합이 각 수들이 계단 수를 가지는 경우의 수이므로 1000000000을 나누고 출력해준다.

---

풀이 결과

10844 풀이 결과