[알고리즘] 동적 계획법(Dynamic Programming) - 백준 10844번 쉬운 계단 수

좋은 풀이 아님!! 배열로 다시 풀기!!

import sys
n = int(sys.stdin.readline().rstrip())

zero, one, two, three, four, five, six, seven, eight, nine = [0] * 100, [0] * 100, [0] * 100, [0] * 100, [0] * 100, [0] * 100, [0] * 100, [0] * 100, [0] * 100, [0] * 100
one[0], two[0], three[0], four[0], five[0], six[0], seven[0], eight[0], nine[0] = 1, 1, 1, 1, 1, 1, 1, 1, 1

if n == 1:
    print((zero[0] + one[0] + two[0] + three[0] + four[0] + five[0] + six[0] + seven[0] + eight[0] + nine[0]) % 1000000000)
else:
    for i in range(n-1):
        zero[i+1] = one[i]
        one[i+1] = zero[i] + two[i]
        two[i+1] = one[i] + three[i]
        three[i+1] = two[i] + four[i]
        four[i+1] = three[i] + five[i]
        five[i+1] = four[i] + six[i]
        six[i+1] = five[i] + seven[i]
        seven[i+1] = six[i] + eight[i]
        eight[i+1] = seven[i] + nine[i]
        nine[i+1] = eight[i]
    
    print((zero[n-1] + one[n-1] + two[n-1] + three[n-1] + four[n-1] + five[n-1] + six[n-1] + seven[n-1] + eight[n-1] + nine[n-1]) % 1000000000)

풀이과정

1. n은 100 이하의 수, 따라서 각 숫자에 [0] * 100 배열을 만든다.
2. 첫 번째 자리에는 0(zero) 이 올 수 없음으로 zero를 제외하고 나머지 숫자 배열의 첫 번째 인덱스에 1을 넣는다.
3. 두 번째 자리를 기준으로,

• 0은 1로부터 나온다.
• 1은 0과 2로부터 나온다.
• 2는 1과 3으로부터 나온다.
  ...
• 9는 8로 부터 나온다.

4. 모든 수를 더한 후 1000000000로 나눈다.