백준 2579 : 계단 오르기 _자바 Java

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

---

<추론과정 ↓>

 

 

계단 개수(n)이고, 각 계단의 점수(a[])가 있을 때, 최대값(dp[])은?

 

n	밟은 계단 경우의 수	dp[]
1	a[1]	a[1]
2	a[1]+a[2] / a[2]	a[1]+a[2]
3	a[1]+a[3] / a[2]+a[3]	Math.max(a[1] ,a[2])+a[3]
4	a[1]+a[3]+a[4] / a[2]+a[4] / a[1]+a[2]+a[4] / a[2]+a[3]+a[4]	Math.max(dp[3],dp[2])+a[4]

a[1]+a[3] / a[2]+a[3] 둘중  dp[3] 에 들어간 값이 max 값.

a[1]+a[3]+a[4] / a[2]+a[4] /a[1]+a[2]+a[4] / a[2]+a[3]+a[4]

==>dp[3]+a[4] vs a[2]+a[4] vs a[1]+a[2]+a[4]  로 줄어듦.

 

a[2]+a[4] vs a[1]+a[2]+a[4] 

이 둘중 dp[2] 에 들어간 값이 a[1]+a[2] 이기 떄문에 

==>dp[3]+a[4] vs dp[2]+a[4] 로 줄어들었음.

 

즉, dp[i-1]과 dp[i-2] 값중 max 값과 a[4]를 더해서 dp[4]에 넣어주면 된다고 추론했음.

 

그래서 나온 식이 dp[i] = Math.max(dp[i-1], dp[i-2]) + arr[i]; 인데, 이걸로  for문 돌리면 틀림.

 

 

Math.max(a[1] ,a[2])+a[3]   와   Math.max(dp[3],dp[2])+a[4] 를 가지고 공통의 규칙을 찾아보자.

 

Math.max(dp[1] ,a[2])+a[3]     Math.max(dp[3],a[1]+a[2])+a[4]

 

Math.max(dp[i-2] ,a[i-1])+a[i]      Math.max(dp[i-1],dp[i-2])+a[4]

Math.max(dp[i-2] ,a[i-1])+a[i]      Math.max(dp[i-2],dp[i-1])+a[i]

=> 전전계단의 누적스코어 vs 전 계단에서 올라오는 스코어 혹은 누적스코어(a[i-1] 과 dp[i-1]이 다름.)

=>두칸 전에서 이번 칸으로 올라오는게 값이 크냐 그 전 칸에서 올라오는게 크냐

 

i=3,  a[i-1]= a[2] =>dp[0]+a[2]

i=4, dp[i-1]=dp[3]=>dp[1]+a[3] 혹은 a[2]+a[3]

 

규칙이 생기려면 

a[i-1] 과 dp[i-1] 를 dp[i-3]+a[i-1] 로 바꾸면 된다...

 

이렇게 찾는게 맞나싶다ㅋㅋㅋ

 

---

 

**

if(n>=2)  dp[2]=arr[1]+arr[2]; 이렇게 if 구문에 안넣어주고 그냥 선언 해줬다가 런타임 에러떴당... 주의하자..

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

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];
		 
		
		for(int i=1;i<=n;i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		
		int[] dp= new int[n+1];
		dp[0]=0;
		dp[1]=arr[1];
		if(n>=2)
			dp[2]=arr[1]+arr[2];
		for(int i=3;i<=n;i++) {
			dp[i] = Math.max(dp[i-2], dp[i-3] + arr[i-1]) + arr[i];
		}

		System.out.println(dp[n]);
	}
	
}