[JAVA] 백준 2579번 【계단 오르기】

---

 

[JAVA] 백준 2156번 【포도주 시식】

 

계단 오르기 문제는 2156 포도주 시식과 비슷한 문제라고 볼 수 있다. 어쩌면 더 쉬운 문제이다.

 

포도주 시식 문제의 경우 마지막 잔을 꼭 마셔야 한다는 조건은 없지만, 계단오르기 문제는 마지막 계단은 꼭 밟아야 한다는 조건이 있다.

 

dp배열에 각 계단 위치에 올랐을 때, 얻을 수 있는 점수의 최댓값을 기록할 것이다.

 

마지막 계단은 꼭 밟아야 한다는 조건 때문에, dp[i]값에는 array[i]값은 무조건 포함이 되어야 하므로, 포도주 시식 문제에서 세웠던 조건 중 Case2 와 Case3 만 고려해서 둘 중에 최댓값을 기록하면 된다.

 

즉 (dp[i-3] + array[i-1] +array[i]) 와 (dp[i-2]+array[i]) 둘 중에 큰 값을 dp[i] 값으로 업데이트 하면 된다!

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.valueOf(br.readLine());
		int[] dp = new int[N + 2];
		int[] array = new int[N + 2];
		for (int i = 1; i <= N; i++) {
			array[i] = Integer.valueOf(br.readLine());
		}
		dp[1] = array[1];
		dp[2] = array[1] + array[2];
			for (int i = 3; i <= N; i++) {

					dp[i] = Math.max(dp[i - 3] + array[i - 1] + array[i], dp[i - 2] + array[i]); 
			}
//		System.out.println(Arrays.toString(array));
//		System.out.println(Arrays.toString(dp));
		System.out.println(dp[N]);
	}
}