[백준] 10844번 쉬운 계단 수 (파이썬)

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

• 해당문제 링크

  목차

1. 문제풀이 아이디어
2. 구현코드

문제풀이 아이디어

• 해당 문제는 1<=N<=100 이므로 순차적으로 모두 접근해서 풀려고 하면 최대 10^100 라는 숫자까지 접근해야하는 문제이다.
• 그렇기 때문에 DP를 이용해서 푼다고 생각한다.
• 처음엔 먼저 작은 경우 겹치는 경우들을 생각해본다.
• N = 1인 경우, 1,2,3,4,5,6,7,8,9 가 전부 계단 수가 되어서 9가 나온다.
• N = 2인 경우, 10, 11, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 이렇게 17개가 된다. 이 경우 겹치는 부분은 10의 자리들이 겹치는 것을 확인할 수 있다.
• 위의 경우에 다른 값들과 다른 부분이 있다. 10의 자리가 9인 경우엔 N=2인 계단 수가 1개만 나온다. N=3을 생각하면 0에서도 1개만 나올 것이다. 1, 9인 경우만 1개가 나오고 나머지에선 2개가 나온다.
• 이 말은 앞에 자리들은 하나도 중요하지 않고 마지막 숫자만 중요하다는 것 -> 마지막 수가 0 ~ 9인 것들의 개수만 센다면 각 길이에서의 계단 수의 개수를 구할 수 있다는 것이다.
• dp 테이블의 크기는 0 ~ 9 까지 10개의 크기로 구성할 것이고 초기화는 개수를 삽입할 것이기 때문에 0으로 초기화할 것이다.
• seed 값은 가장 작은 경우인 N=1일 때, 1~9까지를 1로 삽입한다.
• 각 값에서 -1, +1을 한 값들이 계단 수로 인정될 수 있기에 그 값들에 현재 값의 개수를 삽입한다. 이렇게 삽입하면서 현재 값의 개수는 0이 되는데 -1, +1을 하면서 원소들을 전부 이동시키기 때문이다.
• 이것을 iterate해준다.

  구현코드

  if __name__ == "__main__":
    n = int(input())
    dp = [0]*10
    for i in range(1, 10): # seed 값을 삽입
        dp[i] = 1
    for i in range(2, n+1): # N에 맞게 iterate
        new = [0]*10 # 각 값들의 개수는 -1, +1의 위치로 이동을 하기에 해당 위치의 값은 0이 되는 것
        for j in range(10):
            if j-1>=0: new[j-1] += dp[j]
            if j+1<=9: new[j+1] += dp[j]
        dp = new.copy()
    print(sum(dp)%1000000000)