위 문제는 3가지 조건을 만족해야 한다.
1. 계단을 오를 때, 1단계 또는 2단계씩 오를 수 있다.
2. 연속된 3개의 계단을 밟으면 안된다.(최대 연속 2번만 오르기 가능)
3. 마지막 계단은 반드시 밟아야 한다.
해당 문제는 동적 계획법 문제로써, 필자는 풀이시간 60분을 초과하여 다른 사용자분의 포스팅 및 풀이법을 참고하였다.
풀이 방식에 2가지 방식이 있다고 한다.
- Top-Down
- Bottom-up
동적계획법은 Memoization(메모이제이션)을 통해 연산할 값을 미리 저장해놓는 배열을 의미한다.(연산 결과를 저장해놓음으로써, 성능 향상)
즉, 처음 문제를 접근할 때 메모이제이션을 염두한 뒤, 메모이제이션을 위한 연산을 위해 접근하는 식으로 하면 된다.
🎯 메모제이션 개념 상기
a1 + a2 + a3 + ... +an-1 + an = Sn
a1 + ~ + an-1 = Sn-1 이라는 것을 저장해두면, 실제 Sn을 더할 때,
an만 알면 Sn을 금방 구할 수 있다.
위 문제의 기본적인 알고리즘은 다음과 같다.
static int find(int N) {
if(dp[N] == null) {
dp[N] = Math.max(find(N - 2), find(N - 3) + arr[N - 1]) + arr[N];
}
return dp[N];
}위 식에서 find(N-1) 재귀호출은 하지 않았는데, 이는 dp[4] 이 메모제이션이 되어있다고 할 때, 이전 단계인 N-3 계단을 밟은 상태인지 아닌지 여부를 알 수 없기 때문이라고 한다.
즉, 연속된 3개의 계단을 밟았는지 여부를 판단하기 위해, 직전 계단에 대해 재귀 호출 보다는 실제 계단 값을 넣어주어, 계단 2개를 오르는 경우와
계단 하나를 오르는 경우 중 어느 값이 더 큰지 비교 후 마지막 계단을 오르도록 설계하는 것이 타당하다.(Top-down)
Bottomp-up 방식도 마찬가지이다. 재귀호출이 아닌 반복문을통해서 모든 값들을 채워주는 형식이다.
for (int i = 3; i <= N; i++) {
DP[i] = Math.max(DP[i - 2] , DP[i - 3] + arr[i - 1]) + arr[i];
}
위의 식에서 주의할 점은 i의 값이 3미만으로 설정하게 되면, DP 배열의 -1 인덱스에 접근하게 되므로, ArrayIndexOutOfBoundsException이 발생하게 된다.
😀 Top-Down
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
static Integer dp[];
static int arr[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
dp = new Integer[N + 1];
arr = new int[N + 1];
for(int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
dp[0] = arr[0]; // 디폴트값이 null이므로 0으로 초기화 해주어야한다.
dp[1] = arr[1];
if(N >= 2) {
dp[2] = arr[1] + arr[2];
}
System.out.println(find(N));
}
static int find(int N) {
// 아직 탐색하지 않는 N번째 계단일 경우
if(dp[N] == null) {
dp[N] = Math.max(find(N - 2), find(N - 3) + arr[N - 1]) + arr[N];
}
return dp[N];
}
}😀 Bottom-Up
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] DP = new int[N + 1];
int[] arr = new int[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
// index = 0 은 시작점이다.
DP[1] = arr[1];
// N 이 1이 입력될 수도 있기 때문에 예외처리를 해줄 필요가 있다.
if (N >= 2) {
DP[2] = arr[1] + arr[2];
}
for (int i = 3; i <= N; i++) {
DP[i] = Math.max(DP[i - 2] , DP[i - 3] + arr[i - 1]) + arr[i];
}
System.out.println(DP[N]);
}
}