[백준] 2579번: 계단 오르기(DP, 동적 계획법)

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

2579번: 계단 오르기

코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int stairs = Integer.parseInt(bf.readLine());
		int[] arr = new int[stairs+1];
		int[] dp = new int[stairs+1];
		
		for(int i=1; i<=stairs; i++)
			arr[i] = Integer.parseInt(bf.readLine());
		
		dp[1] = arr[1];			// 첫 번째 계단 -> arr[1]이 최대
		dp[2] = arr[1] + arr[2];// 두 번째 계단 -> 첫번째 + 두번째 계단 합이 최대
		
		for(int i=3; i<=stairs; i++) {
			dp[i] = Math.max(dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i]);
		}
		
		System.out.println(dp[stairs]);
		bf.close();
	}

}

풀이

전형적인 DP(동적 계획법)문제다 ! 

DP는 기본적으로 중복으로 여러번 계산하는 것을 막기위해서 고안된 방법이다.

문제에서 주어진 조건에 따라 규칙을 찾아야 한다. 문제의 조건은 다음과 같다.

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

위와 같다. 

첫 번째는 한 계단 or 두 계단만 오를 수 있는 조건이고,

두 번째는 연속돈 세 개의 계단을 모두 밟으면 안된다 -> 첫번째, 두번째, 세번째... 연속으로 세 계단을 밟을 수 없다.

세 번째는 마지막 계단은 무조건 밟아야 한다는 뜻이다.

 

문제에서 주어진대로 계단이 여섯 번째까지 있다고 가정하면, 어떻게 오르는게 최댓값인지 생각해보면,

계단이 한 개 일때 => 한 계단이 최댓값이다.               dp[1] = arr[1]

계단이 두 개 일때 => 한 계단 + 두 계단이 최댓값이다. dp[2] = arr[1] + arr[2]

계단이 세 개 이상일때 주어진 문제를 기준으로 보면,

 * 일단 마지막 여섯 번째 계단은 무조건 밟아야 한다.

 * 여섯 번째 계단 이전을 생각해보면, 두 가지의 경우가 있다.

    * 1) 만약 여섯 번째 이전 다섯 번째 계단을 밟았을 경우에는 네 번째 계단은 밟을 수 없다.

    * 따라서 세 번째 계단까지의 최댓값 + 다섯 번째 계단 + 여섯 번째 계단이 최댓값이 된다.

    * 2) 만약 여섯 번째 이전에 네 번째 계단을 밟았을 경우에는 다섯 번째 계단은 밟을 수 없다.(by 조건2)

    * 따라서 네 번째 계단까지의 최댓값 + 여섯 번째 계단이 최댓값이 된다.

 

위의 규칙을 기준으로 점화식을 세워보면 아래와 같다.

위 1)의 코드는 아래와 같다.

dp[3] + arr[5] + arr[6]

  -> dp[n-3] + arr[n-1] + arr[n]

 

위 2)의 코드는 아래와 같다.

dp[4] + arr[6]

  -> dp[n-2] + arr[n]

 

위 두 가지 경우의 수 중에 최댓값을 찾아주면 n번째 계단에서의 최댓값을 찾을 수 있다.

 

DP 자세한 풀이 참고

https://sundries-in-myidea.tistory.com/22

[백준 - 2579번] 계단오르기 - 자바(JAVA) 정리 및 해설

 

이거시 초등부 문제 ,,,,,,,,,,,,,