99클럽 코테 스터디 29일차 TIL: 피보나치 DP

오늘의 문제 | 9461. 파도반 수열

DP라고 생각하고, 약간은 피보나치와 비슷하다는 생각이 들었다. 초기 5개까지는 그대로 반영되지만, 그 이후부터는 이전 5개 전의 사이즈와 바로 전 사이즈의 합만큼이 추가된다는 것이다. 물론 N이 작아서 크게 문제될 건 없겠지만 전처리로 100까지의 모든 값을 구하고 접근하려 한다.

dp=[0,1,1,1,2]
for i in range(4,101):
    dp.append(dp[i-4]+dp[i])
for i in range(int(input())):
    print(dp[int(input())])

솔직히 너무 쉬워서 아쉽긴했다. 단순한 피보나치를 구현하는 정도의 난이도였다.

오늘의 회고

DP 문제가 어제에 비해 너무 쉬워졌다. 물론 이거보다 어려운 DP 문제였다면 조금 골치아프긴 했겠지만 아주 단순한 메모이제이션 기법을 사용했다는 생각이 든다.