[BAEKJOON] 2579번 계단 오르기

 

---

이 문제는 첫 번째 계단을 밟는 것을 시작으로 한 칸 혹은 두 칸씩 계단을 오를 수 있다.

단, 첫 번째 계단을 꼭 밟아야 하고, 연속으로 한 칸씩 세 번 반복할 수는 없다. 즉, 한 칸을 오른 다음 한 칸, 그 다음 두 칸 오르기만 가능하다. 

따라서 첫 번째 계단을 오르는 최대 점수는 첫 번째 계단의 가중치인 10점이고,

두 번째 계단을 오르는 최대 점수는 첫 번째 계단을 오른 후에 (첫 번째 계단 10 + 두 번째 계단 20으로 총 30점)이과 바로 두 번째 계단으로 오르는 20점 중 더 높은 점수인 30점 방식으로 계단을 오른다.

세 번째 계단을 오를 때는

1. 첫 번째 계단 → 세 번째 계단  ▶  10 + 20 + 15 = 25

2. 두 번째 계단 → 세 번째 계단  ▶  20 + 15 = 35

위 두 가지 중 최대값은 1. 경우에 해당하기 때문에 세 번째 계단까지 오르는 최대 점수가 45가 된다.

이처럼 이전 결과가 누적되어 영향을 미치는 것을 보아서 DP 유형 문제인 것을 알 수 있다!

어떤 값들이 현재 값에 영향을 미치는지 그림으로 살펴보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N, arr[], sum[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		arr = new int[N + 1];
		sum = new int[N + 1];
		for (int i = 1; i <= N; i++) {
			arr[i] = Integer.parseInt(br.readLine());
		}
		sum[1] = arr[1];
		if (N >= 2) {
			sum[2] = arr[1] + arr[2];
			if(N>=3)
				sum[3] = Math.max(arr[1], arr[2]) + arr[3];
		}
		for (int i = 4; i <= N; i++) {
			sum[i] = Math.max(arr[i - 1] + sum[i - 3], sum[i - 2]) + arr[i];
		}
		System.out.println(sum[N]);
	}
}

[출처]

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

2579번: 계단 오르기