백준 2579번 계단 오르기 [DP] :: 마이구미

이번 글은 백준 알고리즘 2579번 "계단 오르기" 문제를 다뤄본다.

일단 문제를 보자.

이 문제는 동적계획법으로 접근하는 문제이다.

문제에서 친절하게 규칙 3가지를 알려주었다.

먼저 3번 규칙을 보면, 마지막 계단은 무조건 밟는다는 것이 규칙이다.

그렇다면, 마지막 계단을 밟았을 경우, 이전의 경우를 2가지로 생각할 수 있다.

1. 마지막 계단 전의 계단을 밟은 경우.

2. 마지막 계단 전의 계단을 밟지 않은 경우.

1번의 경우에는 마지막 계단 전의 계단을 밟았음으로, 마지막 계단 전전의 계단은 밟지 못한다.

2번의 경우에는 마지막 계단 전의 계단을 밟지 않았음으로, 마지막 계단 전전의 계단을 밟고 왔다.

위 경우를 통해 점화식을 도출해보자.

1. dp[n] = dp[n-3] + array[n-1] + array[n]
2. dp[n] = dp[n-2] + array[n]

dp 배열은 합을 구하는 배열이고, array 배열은 계단의 값이다.

2개의 배열을 이용하는 이유는 dp 배열 하나만 쓸 경우에는 dp[i]의 연속 여부를 확인하기 힘들기 때문이다.

문제는 답은 최대값을 찾는 것이기 때문에 위 점화식 2개를 비교하면서 큰 값을 넣으면 된다.

dp[n] = max(dp[n-3] + array[n-1] + array[n], dp[n-2] + array[n]

위와 같이 최종 점화식을 만들 수 있다.

for(int i=3;i<n;i++) {
    dp[i] = max(dp[i-2] + array[i], dp[i-3] + array[i] + array[i-1]);
}

전체 소스는 아래 Github 링크를 통해 확인하길 바란다.

이만 안녕.

백준 2579번 계단 오르기 문제

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

백준 2579번 문제 전체 소스

https://github.com/hotehrud/acmicpc/blob/master/dp/2579.java