[백준] 2579 계단 오르기 - Java

 

 

 

dp배열에는 해당하는 계단을 밟을 때 얻을 수 있는 최대 점수가 들어간다.

 

세 번 연속으로 계단을 올라가면 안되는 조건이 있기에 dp배열을 두 개 생성해서 하나는 바로 전 계단을 밟은 배열, 나머지는 바로 전 계단을 밟지 않은 배열으로 설정해서 얻을 수 있는 점수의 최댓값을 구하자.

 

 

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

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][2];
			int[] arr = new int[N+1];

			for(int i=1; i<N+1; i++){
				arr[i] = Integer.parseInt(br.readLine());
			}

			dp[1][0] = 0;
			dp[1][1] = arr[1];
			
			if(N >= 2){
				dp[2][0] = arr[2];
				dp[2][1] = arr[1] + arr[2];
			}

			for(int i=3; i<N+1; i++){
				dp[i][0] = Math.max(dp[i-2][0] + arr[i], dp[i-2][1] + arr[i]);
				dp[i][1] = dp[i-1][0] + arr[i];
			}

			System.out.println(Math.max(dp[N][0], dp[N][1]));
			
			
	}
}