99클럽 코테 스터디 2일차 TIL + 피보나치 비스무리한 수열

https://www.acmicpc.net/problem/14495

 

- 오늘의 학습 키워드

DP, 피보나치 응용

 

- 풀이

 

• f(n) = f(n-1) + f(n-3)이라는 점화식을 기반으로 dp[] 배열을 만들어서 반복문으로 값을 계산
• 초기값 f(1), f(2), f(3)는 모두 1로 고정되어 있으므로, 4부터는 점화식에 따라 누적 계산
• 시간 제한이 넉넉하므로 재귀 대신 반복문을 사용해 효율적인 풀이 구현

 

- 오늘의 회고

처음엔 기존 피보나치처럼 f(n) = f(n-1) + f(n-2)일 줄 알았지만, 이 문제는 f(n-3)이 포함된 특이한 점화식이었다.

단순 재귀로 풀려고 하면 호출이 너무 많아져서 시간 초과가 날 것 같았다

 

그래서 메모이제이션 없이 반복문으로 dp[] 배열에 값을 저장하면서 계산하는 방법을 사용했다.

초기값 3개만 지정해주고, for문으로 4부터 n까지 값을 누적 계산하니 빠르게 해결됐다!