[백준] 2579 : 계단 오르기 JAVA 풀이

정말 어렵다............

어렵다는 말만 오백번째 하고 있는 것 같은데 아직 DP문제에 익숙하지 않으니 어쩔 수 없다.

 

그래도 각 계단의 점수와 최댓값을 저장하는 배열을 따로 만들어야 하는 것이나

초기화하는 부분이라도 생각해냈으니 걸음마는 뗀 수준이라 자축해보겠다 흑흑

 

이 문제에서 중요한 조건은 연속된 계단 세 개를 모두 밟을 수 없다는 것이다.

 

V		V	V
?	V		V

그럼 계단을 밟을 수 있는 건 이렇게 두 경우가 된다.

 

한 칸 전 계단을 밟았으면 두 칸 전 계단은 반드시 밟지 말아야 한다.

한 칸 전 계단을 밟지 않았다면 두 칸 전 계단은 반드시 밟아야 한다.

이 두 경우 중에 최댓값을 저장하면 되는데, 이를 코드로 쓰면 다음과 같다.

// dp는 그 계단까지의 최댓값을 저장하는 배열
// arr는 각 계단의 점수를 저장하고 있는 배열
dp[N] = Math.max(dp[N-3]+arr[N-1], dp[N-2])+arr[N];

 

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

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[] arr = new int[N+1];
        // 그 계단까지의 최댓값을 저장할 배열
        int[] dp = new int[N+1];
        
        // 계단의 점수를 입력받아서 배열에 저장
        for(int i=1;i<=N;i++) {
        	arr[i] = Integer.parseInt(br.readLine());
        }
        
        // 최댓값을 계산하기 위한 초기값
        // 첫번째 계단에서의 최댓값은 첫번째 계단의 점수 자체
        dp[1] = arr[1];
        
        // N으로 1이 입력될 수도 있으므로 예외처리해줌
        if(N>=2) {
            dp[2] = arr[1]+arr[2];
        }
        
        // 3개 전 계단과 직전 계단을 밟았을 때와
        // 2개 전 계단을 밟았을 때 중 더 큰 값을 구하고
        // 현재 계단의 값을 더한 뒤 저장함
        for(int i=3;i<=N;i++) {
        	dp[i] = Math.max(dp[i-3]+arr[i-1], dp[i-2])+arr[i];
        }
        
        // 마지막 계단에서의 최댓값 출력
        System.out.println(dp[N]);
        
    }
}