lgvv98

BOJ 2579 계단 오르기 ✅ 점화식을 이용한 DP문제였다. 나동빈 책을 공부하면서 비슷한 문제를 해결하려는 노력을 했었는데, 진짜 너무나도 어려웠다. 여기서는 점화식을 세우기 위해 문제의 마지막 조건의 초점을 맞추는데, 마지막 계단은 꼭 밟아야 한다. 이 문장을 기준으로 점화식을 설계해보자!!!! 마지막 계단을 꼭 밟아야 하므로, 마지막 계단을 밟는 케이스를 보자면1. O X O O (끝 계단과 바로 이전 계단을 밟음, 3연속은 안된다, 근데 최댓값을 찾아야 하므로 전전전칸도 포함한다.)2. ? O X O(끝 계단과 그 전전 계단을 밟음) 케이스 1에서는 끝 패턴이 저걸로 고정 케이스 2에서는 끝 패턴이 저렇게 고정 ? 자리는 어떤게 올지 모른다는 말 -> 따라서 수식에 반영하지 않는다. 이를 점화식..