백준 2579번 : 계단 오르기

 

규칙 세 가지를 지켜서 계단을 오르는 최댓값을 고르는 문제이다.

 

지켜야 할 규칙 

1. 계단은 한 계단씩 또는 두 단계씩만 오를 수 있다.

2. 세 개의 계단을 연속적으로 밟을 수 없다.

3. 마지막 계단은 꼭 밟는다.

 

주의할 점.

1. 최댓값을 찾는데다가 밟을지 안 밟을지도 고려해야 하므로, 그 전의 기록을 계속 갖고 있어야 해서 기록을 하는 dp 배열이 필요하다.

2. 계단을 한 개 또는 두 개를 밟고 세 개를 연속적으로 밟을 수 없다는 것은, 지금의 계단에서 총 3개 아래의 값을 모두 확인해야 한다.

 

1. 첫 번째 계단을 밟는 경우.

 - 첫 번째 계단을 밟을 때 최댓값일 것이다.

 dp[0] = arr[0]

 

2. 두 번째 계단을 밟을 경우,

 - 두 번째 계단을 밟을 땐, 최댓값은 두 계단을 모두 밟는 경우일 것이다.

dp[1] = arr[0] + arr[1] 

 

3. 세 번째 계단을 밟을 경우,

 - 연속으로 3 계단을 못 밟는 2번 규칙과 한 번에 한 개나 두 개씩만 밟을 수 있다는 1번 규칙을 고려해야 한다.

 경우의 수를 따진다면, 두 가지의 방법이 있을 것이다.

dp[2] = arr[0] + arr[2]    or    arr[1] + arr[2]

 

4. 네 번째 계단을 밟을 경우, 아래의 방법이 있을 것이다.

 - dp[3]  = 1) arr[0] + arr[1] + arr[3]    

               = 2) arr[1] + arr[3]    (=> 첫 번째 계단은 안 밟고 두 번째 계단부터 밟는 것이므로, 1)보다 무조건 작을 수밖에 없다. )

              = 2) arr[0] + arr[2] + arr[3]   

 즉, 네 번째 계단을 밟을 때에는 

   - 두 번째 계단을 밟고 네 번째 계단을 밟는 경우

   - 첫 번째 계단을 밟고 세 번째 계단을 밟은 후, 네 번째 계단을 밟는 경우

이렇게 두 가지로 나뉘는 걸 알 수가 있다.

 

5. 다섯 번째 계단을 밟을 경우, 

 - dp[4] = 1) arr[0] + arr[1]   + arr[3]  + arr[4] 

                                => 첫 번째 계단(까지) + 3번째 계단 + 4번째 계단 (arr[0] + arr[1] 은 dp[1]의 값이기도 하다.)

             = 2) arr[1]  + arr[3]  + arr[4]   (  1) 보다 무조건 작다.)

             = 3) arr[1]  + arr[2]  + arr[4]   

             = 4) arr[0] + arr[2]  + arr[4]   

                              => 3)과 4)는 두 번째 계단(까지)을 밟는 경우 + arr [4]라고 볼 수 있다.

결국, 

- 두 번째 계단까지 + 네 번째 계단 + 다섯 번째 계단

- 세 번째 계단 + 다섯번째 계단

위의 두 가지의 경우이다.

 

 

이것을 식으로 세워보면, 

dp [n] = Math.max(dp[n-3]+arr[n-1]+arr[n] , dp[n-2] + arr[n])

import java.util.Scanner;

public class Main {
	private static Scanner sc;
	private static int n = 0;
	public static void main(String args[]) {
		sc = new Scanner(System.in);
		n = sc.nextInt();
		
		int arr[] = new int[n+3];
		int dp[] = new int[n+3];
		
		for(int i=0;i<n;i++) {
			arr[i]=sc.nextInt();
		}	
		dp[0] = arr[0];
		dp[1] = Math.max(arr[0]+arr[1],arr[1]);
		dp[2] = Math.max(arr[0]+arr[2], arr[1]+arr[2]);
		
		for(int i=3;i<n;i++) {
			dp[i]=Math.max(dp[i-3]+arr[i-1]+arr[i],dp[i-2]+arr[i]);
			
		}
		System.out.println(dp[n-1]);
		
	}
	
}