132. 2579(계단 오르기)

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		ArrayList<Integer> stair = new ArrayList<>();
		ArrayList<Integer> dp = new ArrayList<>();
		
		int N = Integer.parseInt(br.readLine());
		
		for(int i=0;i<N;i++) {
			stair.add(Integer.parseInt(br.readLine()));
		}
		try {
		dp.add(stair.get(0));// dp[0]
		dp.add(Math.max(stair.get(0)+stair.get(1), stair.get(1)));// dp[1]
		dp.add(Math.max(stair.get(0)+stair.get(2), stair.get(1)+stair.get(2)));// dp[2]
		
		for(int i=3; i<N; i++) {
			dp.add(Math.max(dp.get(i-3)+stair.get(i-1)+stair.get(i),dp.get(i-2)+stair.get(i)));
		}
		
		}
		catch(Exception e) {
			int sum = 0;
			for(int val:stair) {
				sum += val;
			}
			dp.add(sum);
		}
	System.out.println(dp.get(dp.size()-1));
	}

}

문제요약

마지막 계단을 올랐을 때 최대값을 구하라.

조건 1. 연속 세개의 계단을 올라갈 수 없다.

조건 2. 마지막 계단은 반드시 밟아야 한다.

설명

그림으로 큰 틀은 이해가 될 것이다.

dp.add(stair.get(0));// dp[0]
dp.add(Math.max(stair.get(0)+stair.get(1), stair.get(1)));// dp[1]
dp.add(Math.max(stair.get(0)+stair.get(2), stair.get(1)+stair.get(2)));// dp[2]

 

어쩔 수 없이 dp[0],dp[1],dp[2] 는 따로 계산이 필요하다. 

dp.add(Math.max(dp.get(i-3)+stair.get(i-1)+stair.get(i),dp.get(i-2)+stair.get(i)));

 

 

네번째 계단부터는 비교가 가능하다.

직전칸에서 올라온 경우와, 전전칸에서 올라온 경우를 따져 가장 큰 수를 더해나가면 된다.

의문점

 

1. 입력값이 7이 었다면?

dp에서는 각 계단별로 최댓값을 가지고 있다.

따라서 7에서 다시 위와 같은 식을 사용해서 계산을 할 수 있다.

 

2. 계산하는 계단의(dp) 최댓값이 직전칸에서 올라온 경우의 최댓값이었다면?

위와 같은 사고를 방지하기 위해서 dp[i-3] 혹은 dp[i-2]로 계산한다.

따라서 전 계단의 dp를 사용하지 않아 위와같은 오류가 나올 수가 없다.

 

주의점

계단수가 2칸까지 나올 수 있다.

따라서 이에 대한 처리가 따로 필요하다.

예외 처리를 통해 2칸일 경우는 따로 값을 받는 방법을 채택하였다.

 

[출처]https://daimhada.tistory.com/181