문제 N개의 계단이 있고 각 계단 위에는 임의의 정수가 적혀있다. 철수는 첫 번째 계단에서 마지막 계단까지 올라가려 하는데 한 번에 오를 수 있는 계단수는 1개 또는 2개이다. 계단을 오르는 비용이 (현재 계단에 적혀있는 정수) - (옮겨갈 계단에 적혀있는 정수)의 절대값이라고 할 때 최소 비용을 구하시오. 풀이 일단 각 계단에 적힌 정수를 h(i)라고 하자. 그러면 첫 번째 위치 h(1)에서 한 계단을 오르는 비용은 |h(1) - h(2)| 이고 두 계단을 오르는 비용은 |h(1) - h(3)| 이 된다. 제일 먼저 떠오르는 순진한 방법은 greedy하게 각 계단에서 비용이 적은 층으로 옮겨가는 것이다. 즉, 단순히 각 계단에서 한 계단 오르는 비용과 두 계단 오르는 비용 중에서 적은 방법을 선택해서 ..