문제 이해

계단마다 수치가 존재한다.
가장 꼭대기 계단까지 오르고 싶은데, 2가지 조건이 존재한다.

1. 계단을 밟으면 다음 계단이나(1칸 이동), 다다음 계단(2칸 이동)만 가능하다.

2. 세 개 계단을 연속해서 밟을 수 없다.

꼭대기 계단까지 올라가는 과정에서 밟은 계단의 수치를 더할 것이다. 이 때 더한 수치의 합이 최대가 될 때의 합을 구하는 문제이다.

---

문제 풀이

현재 내가 밟고 있는 계단은 어떻게 오를 수 있었을까?

1. 2칸 전에 있는 계단에서 바로 올라왔다.

2. 1칸 전에 있는 계단에서 바로 올라왔다.

그런데, 우리는 2번 방법에서 제한 조건이 있는 것을 알 수 있다.

"세 개 계단을 연속해서 밟을 수 없다"

즉, 2번 방법으로 현재 위치 계단으로 올라왔다면, 무조건 1칸 전에 있는 계단을 올라갔을 때는 3칸 전의 계단에서 바로 올라오는 상황이여야 한다.
(즉, 3번째 전 계단 ⇒ 1번째 전 계단 ⇒ 현재 계단)

따라서, DP를 2차원 배열로 생각하여 1번 방법으로 현재 계단에 도착했는지, 2번 방법으로 현재 계단에 도착했는지 저장하기로 하였다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[][] answer;
    //answer[i][0] : i-2번째 계단 -> i번째 계단
	//answer[i][1] : i-1번째 계단 -> i번째 계단

	static int[] cost; // 계단의 수치
	
	
	static void dp() {
		answer[1][0] = cost[1];
		
		for(int i =2;i<N+1;i++) {
			answer[i][0] = Math.max(answer[i-2][0],answer[i-2][1])
            												+cost[i];
            // i-2번째 계단 -> i번째 계단의 방법
            // i-3 -> i-2 -> i번째, i-4 -> i-2 -> i번째 계단을 올라오는
            // 방법 모두 가능하다
            // 최댓값을 구하고 싶었기 때문에, 
            // answer[i-2][0], answer[i-1][1] 중 더 높은 값을 사용한다.
			
            answer[i][1] = answer[i-1][0]+cost[i];
            // i-1번째 계단 -> i번째 계단의 방법
            // i-3 -> i-1 -> i번째 방법으로 계단을 오르는 방법만 가능하다
            // answer[i-1][0] + cost[i]값만 answer[i][1]이 될 수 있다.
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		
		answer = new int[N+1][2];
		cost = new int[N+1];

		for(int i =1;i<N+1;i++) {
			cost[i] = sc.nextInt();
		}
		
		dp();
		
		System.out.println(Math.max(answer[N][0],answer[N][1]));
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과