아이테킨의 끄적끄적

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제의 조건은 세가지다. 1. 연속된 세개의 계단을 밟으면 안됨 2. 마지막 계단은 밟아야함 3. 한칸 또는 두칸씩 이동 가능함. 마지막 계단은 밟아야하므로 i번째 계단이라고 한다면 max(i-2번째 계단을 밟고 두칸을 뛰어 i번째로 온 경우, i-3번째 계단을 밟고 i-1번째를 밟고 i번째로 온 경우) 이런식으로 점화식을 만들면 된다. 코드 # 2579 - 계단 오르기 n = int(input()) step..

∴다이나믹 프로그래밍에 대한 개념정리 및 예제풀이 마지막으로 DP 정복하는것을 향해서!!! 다이나믹 프로그래밍(Dynamic programming, DP)란? 다이나믹 프로그래밍이란 복잡한 하나의 문제를 간단한 여러개의 중복되는 문제로 나누어 같은 방식으로 풀어 답을 구하는 방법을 말한다. 나는 보통 동적(Dynamic)이라는 용어를 보면 '계속해서 움직이는' 이라는 뜻으로 이해했다. 그러나 여기서의 동적(dynamics)이라는 단어는 DP를 이해하는데 직관적으로 도움을 주지 못하는듯 하다. 뒤에서 언급하겠지만 그보다는 '작은 중복문제들을 기억하며 푼다'라는 의미로 받아들이는 것이 좋을 것 같다. 그래서 앞으론 dyanmic programming보다는 DP라고 부르려고 한다. (사실 이렇게 해야 나도 헷..