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

·
📝 끄적끄적/항해99 코테 스터디
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[] 배열에 값을 저장하면서 계산하는 방법을 사용했..