문제 링크

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


DP가 무엇인지 묻는 문제이나 DP문제를 처음풀어서 어려웠다

DP는 규칙을 구하는 문제이구나 라는걸 느꼈다.

하지만 DP는 어떤 선택을 하느냐에 따라 문제가 변형되는지라, 점화식을 찾는게 많이 어려운거 같다 (백준 약 문제 풀다가 느낌)


아무튼 첫 DP 문제였다.


Think


DP[n] = DP[n-1] + DP[n-2] + DP[n-3]





풀이


1. 첫 풀이



- 탑다운 (2^n)

- 시간초과

- n <= 1000000 이기 때문

- 재귀를 첨써서 n이 크면 아예 재귀를 쓰면 안 되는걸 몰랐다 (그냥 고려를 안했다)



2. 두 번째 풀이



- 바텀업 (mn)

- 메모리 초과



3. 세 번째 풀이


사실 2번째까지 하고 고민하다가 모르겠어서 남의 풀이를 봄




- n이 max일 때의 memo를 구한 후 남은 케이스는 인덱스로 접근(n)

- 결국 테스트케이스 또한 max 케이스의 부분합이기 때문이다

- 이걸 완전히 고려를 못했음. 저런 말랑말랑한 사고능력을 배워야겠다.



결론

DP가 너무 어렵다

말랑말랑 사고방식을 갖추지 않는다면 나중에 코테 볼때 에러 터트리다가 못풀고 끝낼거같다