방학공부 2일차

계속해서 DP문제를 풀어보자.

문제 : 백준 10844번
알고리즘 : DynamicProgramming

풀이를 먼저 보면

import sys
input = sys.stdin.readline

function = [[0,0,0,0,0,0,0,0,0,0] for i in range(101)]
function[1] = [0,1,1,1,1,1,1,1,1,1]
#main
N = int(input())
i = 1
while(i < N) :
    function[i + 1][0] = function[i][1]
    function[i + 1][9] = function[i][8]
    for index in range(1,9):
        function[i + 1][index] = function[i][index - 1] + function[i][index + 1]
    i += 1
sum = 0
for el in function[N]:
    sum += el
print(sum % 1000000000)

길이가 N인 계단 수의 마지막 자리는 0,1,2,''',9가 가능하다. ex) N : 5 => 1 2 1 0 1

N : 1인 경우를 첫 항으로 잡고 N >= 2에 대해 연산을 수행한다.

길이가 N이고 마지막 자리가 0인 계단 수의 수 = 길이가 N-1이고 마지막 자리가 1인 계단 수 의 수
길이가 N이고 마지막 자리가 9인 계단 수의 수 = 길이가 N-1이고 마지막 자리가 8인 계단 수 의 수

길이가 N이고 마지막 자리가 Index(= 1 ~ 8)인 계단 수의 수 =
길이가 N-1인 마지막 자리가 (Index-1)인 계단 수의 수 + 마지막 자리가 (Index+1)인 계단 수의 수

위의 연산으로 인덱스 2부터 N까지 리스트를 채워나갔다. 사실 너무 무식한 방법이 아닌가 싶어서 조금 염려되었는데 입력이 100이하의 자연수이므로 큰 문제없을 것으로 생각했고, 다행히 성공했다.

문제 제대로 안 읽고 %연산 안하고 제출해서 1회 실패...

종합 평가

시간복잡도 : avr = O(n)
소요 시간 : 10분전후
실패 횟수 : 1