문제 출처: https://www.acmicpc.net/problem/2579
문제
계단 오르는 데는 다음과 같은 규칙이 있다.
계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
private static int[] stairs;
private static int[] scores; // 메모이제이션 용
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(reader.readLine());
stairs = new int[N + 1]; // 각 계단별 점수 저장용
scores = new int[N + 1]; // 계단별까지의 최댓값 저장용
Arrays.fill(scores, -1);
for (int i = 1; i <= N; i++) {
stairs[i] = Integer.parseInt(reader.readLine());
}
scores[0] = stairs[0]; // dummy 값
scores[1] = stairs[1]; // 1번 계단까지의 최댓값은 그냥 1번 계단의 수
if (N >= 2) scores[2] = stairs[1] + stairs[2]; // 들어오는 수는 자연수로, 1이 들어올 때를 대비하여 처리. 2번 계단까지의 최댓값
System.out.println(dynamicPrograming(N));
}
private static int dynamicPrograming(int stair) {
if (scores[stair] == -1) { // 아직 값이 등록이 안 된 경우
scores[stair] = Math.max(dynamicPrograming(stair - 2), dynamicPrograming(stair - 3) + stairs[stair - 1]) + stairs[stair];
}
return scores[stair];
}
}