2579
-
백준 2579번 계단 오르기 [DP] :: 마이구미알고리즘 풀이/동적계획법 2017. 1. 16. 22:58
이번 글은 백준 알고리즘 2579번 "계단 오르기" 문제를 다뤄본다.일단 문제를 보자. 이 문제는 동적계획법으로 접근하는 문제이다.문제에서 친절하게 규칙 3가지를 알려주었다.먼저 3번 규칙을 보면, 마지막 계단은 무조건 밟는다는 것이 규칙이다. 그렇다면, 마지막 계단을 밟았을 경우, 이전의 경우를 2가지로 생각할 수 있다.1. 마지막 계단 전의 계단을 밟은 경우.2. 마지막 계단 전의 계단을 밟지 않은 경우. 1번의 경우에는 마지막 계단 전의 계단을 밟았음으로, 마지막 계단 전전의 계단은 밟지 못한다.2번의 경우에는 마지막 계단 전의 계단을 밟지 않았음으로, 마지막 계단 전전의 계단을 밟고 왔다. 위 경우를 통해 점화식을 도출해보자. 1. dp[n] = dp[n-3] + array[n-1] + array..