이 문제는 거의 한 1년 전에, DP를 처음 배우면서 접했던 문제다.
알고리즘을 배운지 한 달 정도밖에 안 됐던 당시에는, 어떻게 접근해야할지 감조차 안 잡혔다.
왜냐면 계단 세 개를 연속해서 오를 수가 없기 때문에, 그럼 그것을 계속 고려해서 앞의 칸들의 최댓값을 결정지을 때 어떻게 올라왔는지(전 계단을 밟았는지, 전전 계단을 밟았는지)를 전부 기억해야되지 않나..? 라고 생각했기 때문에 그랬다.
하지만 결국에는 그것 마저도 생각해서 식을 세울 수가 있었다.
그리고 그 식을 흔히 점화식이라고 한다.
이 점화식을 세울 때는 해당 N값이 어떻게 만들어지는 지에 집중하면 쉽게 세울 수 있었다.
만약 DP가 처음이라면, SWEA 4869: 종이붙이기 이 문제를 먼저 풀어보길 추천한다!!
내가 예전에 풀었던 DP문제 풀이방법을 (이제는 안 쓰는) 네이버 블로그에 정리해놓은 글이다ㅎ 이해하기 쉬울 것이다!!
그렇다면 이 문제에서 N번 째 계단은 어떻게 결정될까?
연속하는 세 계단을 밟을 수가 없으니까, 두 경우의 수가 존재한다.
- 바로 전 계단
(N-1)을 밟은 경우,N-3번 째 계단을 밟아야 한다.- 전전 계단
(N-2)을 밟은 경우, 앞의 상황을 고려하지 않아도 된다.
위 두 가지 경우에서 더 큰 값을 구하면 된다.
그럼 위의 이 두 가지만 고려하면 모든 경우를 포함할 수 있다.
왜 그렇게 될까?
우리가 N번 째 계단을 생각할 때, 세 계단을 연속해서 밟으면 안 된다는 점을 생각해서 식을 세웠다.
우리는 특정 N번째 계단을 밟을 때, 이전까지의 DP 값들이 이미 규칙을 만족하면서 최적의 해를 갖고 있다고 가정한다. 그래서 우리는 새로운 계단(N번 째 계단)을 밟을 때, 바로 직전의 상태(N-1 또는 N-2)만 고려하면 되는 것이다.
실제로 1번을 생각해보자, N-1번 째 계단을 밟고나서, N-3번 째 계단을 밟게 된다면, 중간의 N-2번 째 계단을 건너뛰었기 때문에, 규칙을 만족한다. 즉, 다시 N번째 계단에서와 같은 방식으로 최적의 선택을 하면 된다.
2번을 생각해보자, N-1번 째 계단을 건너 뛰고 N-2번 째 계단을 밟았기 때문에, N번 째 계단과 같은 상황이 된다.
즉, 규칙을 지키는 선에서 각 계단의 최적해만 구해나가다 보면 결국에 전체의 최적해를 구할 수 있는 것이다.
다른 문제에도 적용하기 위해서 좀 더 일반적으로 생각해보자면, 같은 상황이 반복되는 것을 캐치해서 점화식으로 표현하면 된다!
우리의 식은 이렇게 된다.
-
바로 전 계단을 밟는 경우
DP[N] = Stair[N] + Stair[N-1] + DP[N-3] -
전전 계단을 밟는 경우
DP[N] = Stair[N] + DP[N-2]
이 둘 중 최댓값을 DP[N]으로 저장하면 된다!
그래서 최종식의 형태는 이렇게 된다.
DP[N] = Stair[N] + max(Stair[N-1] + DP[N-3], DP[N-2])
정답
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// N 입력 받기
int N = Integer.parseInt(br.readLine());
// 계단 입력 받기
int[] stair = new int[N + 1];
for (int i = 1; i <= N; i++) {
stair[i] = Integer.parseInt(br.readLine());
}
// 1. 기본 세팅
int[] DP = new int[N + 1];
DP[1] = stair[1];
if(N != 1) DP[2] = DP[1] + stair[2];
// 2. DP
for (int n = 3; n <= N; n++) {
DP[n] = stair[n] + Math.max(stair[n - 1] + DP[n - 3], DP[n - 2]);
}
System.out.println(DP[N]);
}
}