백준 9461 파도반 수열 / 파이썬 알고리즘

백준 9461 파도반 수열 / 파이썬 알고리즘

www.acmicpc.net/problem/9461

9461번: 파도반 수열

n = int(input())

save = {

}
save[1] = 1
save[2] = 1
save[3] = 1
save[4] = 2
save[5] = 2


for _ in range(n):
    pn = int(input()) # pn입력값 받고
    for k in range(6, pn+1): #하나의 입력값에 대해서 for문을 돌린다.
        save[k] = save[k-1] + save[k-5]
        # 6이상 pn의 공식
        # save[6] = save[5] + save[1]
        # save[7] = save[4] + save[2]
        # . . . . .
        # save[9] = save[8] + save[4]
        # save[10] = save[9] + save[5]
    print(save[pn])

동적계획법을 이용해 풀 수 있다.

 

처음 삼각형 그림을 보고 공식을 유추하기 쉬웠다.

 

긴 삼각형의 변의 길이가 n이라 했을때 변의 길이가 n = [n-1]+[n-5] 이었다.

 

숫자 1 ~ 5 까지는 모두 1과 2로 고정값이라

 

save에 1과 2를 따로 넣어줬다.

 

부등호를 이용해서 넣을 수도 있겠지만 그냥 이렇게 제출해도 맞았다.

 

입력값을 입력할 for문을 돌리고,

 

구할 값인 P(N)의 for문을 돌린다.

 

이때 이미 save에 1~5만큼이 있기 때문에 6부터 돌리고, 범위의 끝은 미만이기 때문에 +1 해준다.

 

포문이 계속해서 돌고,

 

마지막에 딕셔너리에 값에 저장되었을 save[pn]을 출력한다.