[백준] 2579 계단 오르기 - DP(동적계획법, Dynamic Programming) JAVA

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

2579번: 계단 오르기

코드설명

DP 문제입니다.

 

이 문제의 경우, 계단 오르는 개수를 구하는 것이 아닌, 점수를 구하는 문제입니다.

 

문제로직입니다.

각 계단을 오르는 최대의 점수를 dp[] 라고 선언합니다.

 

첫번째 계단을 오르는경우,

dp[1] = arr[1] 입니다.

 

두번째 계단을 오르는 경우,

dp[2] = arr[1] + arr[2] 입니다. ( 두개의 계단을 거치는것이 무조건적으로 최대값입니다. )

 

세번째 계단을 오르는 경우,

dp[3] = Math.max(arr[1] + arr[3], arr[2] + arr[3] ) 입니다. 3개의 계단을 연속해서 오르지 못하니 arr[1] + arr[2] + arr[3] 은 불가합니다.

 

네번째 계단을 오르는경우는

dp[4] = Math.max(arr[1] + arr[2] + arr[4], arr[1] + arr[3] + arr[4], arr[2] + arr[4] ) 입니다.

여기서 겹치는 것을 볼 수 있습니다.

 

1. arr[1] + arr[2] + arr[4] 는 첫번째 계단, 두번째 계단, 네번째 계단으로 이동하는 것을 의미합니다.

2. arr[1] + arr[3] + arr[4]는 첫번째 계단, 세번째 계단, 네번째 계단으로 이동하는 것을 의미합니다.

3. arr[2] + arr[4] 는 두번째 계단, 네번째 계단으로 이동하는것을 의미합니다. 

문제를 보면, 첫번째 Case와 세번째 Case에서 arr[2]가 겹치는것을 볼 수 있습니다.

첫번째 Case의 arr[1] + arr[2] + arr[4] 와 arr[2] + arr[4]는 arr[2] 값이 겹치는데 이떄 arr[2]값은 앞서서 우리가 dp[2]라고 정리해놓았습니다. 그렇기에 dp[2] + arr[4] 입니다. 일반화하면, dp[i-2] + arr[i] 입니다. 여기서 헷갈릴 수 잇는 점은 dp[i-3] + arr[i-2] + arr[i]로 표현하는게 맞지 않나라는 생각이 들 수 있습니다. 하지만, 그렇게 할경우 arr[2] + arr[4]값은 고려하지 않으면서 최대값을 구할 수 없습니다. 이미 dp[i-2]를 통하여 앞의 것들의 최대값을 가져온 값을 가져와야 dp[i]가 최대값으로 갱신됩니다. 

 

두번쨰 Case의 arr[1] + arr[3] + arr[4]같은경우가 헷갈립니다. 여기서 dp[3] + arr[4]를 해야하는건가? 라는 궁금증이 생깁니다. 하지만, dp[3]을 더할경우 dp[3]의 최대값이 만약 arr[2]+arr[3] 이었다면 arr[4]도 더해짐으로써 3개의 계단을 동시에 이동한것과 같이 됩니다. 그것은 규칙에 위반되므로 우리는 시작점의 DP값을 더해야만 계단을 3계단 연속적으로 이동하는 경우를 피할 수 있습니다. 여기서 시작점은 arr[1] 입니다. 그러므로 dp[1]을 더하면 되고, 식으로 일반화한다면 dp[i-3] + arr[i-1] + arr[i] 로 정리할 수 있습니다.

 

두번쨰 방법은 재귀적으로 구현합니다.

이는, 계단의 마지막 칸은 항상 추가되어야 하니, 마지막 칸에서부터 계단을 내려오게 합니다.

이렇게 고정된 순서를 원활하게 처리하기 위해 마지막 계단부터 내려가게 처리하면 최적 부분 구조로 문제해결이 가능합니다.

 

코드

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

public class Main {
	public static int T, N;
	public static int answer = 0;
	public static int[] arr;
	public static int[] dp;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	
    	arr = new int[301];
    	dp = new int[301];
    	
    	for(int i=1;i<=N;i++) {
        	st = new StringTokenizer(br.readLine());
        	arr[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	dp[1] = arr[1];
    	dp[2] = arr[1] + arr[2];
    	dp[3] = Math.max(arr[1] + arr[3], arr[2]+arr[3]);
        
    	for(int i=4;i<=N;i++) {
    		dp[i] = Math.max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i]);
    	}
    	
    	System.out.println(dp[N]);
    }
    
}

 

재귀적으로 구현합니다.

처음에 맨 처음 계단에서부터 마지막 계단까지 올라가도록 처리하려고 하였지만, 마지막 계단은 반드시 포함되어야 하므로 반드시 이전 정보를 가지고 있었어야 했습니다.

하지만, 마지막 계단부터 처리한다면 문제가 아래와 같이 처리가능해집니다. 

package Main;

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

public class Main {
    public static int N, K;
    public static int answer = 0;
    public static int[] arr;
    public static int[] cache;
    public static int[] prefixSum;
    public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		cache = new int[N+1];
		Arrays.fill(cache, -1);
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			arr[i] = Integer.parseInt(st.nextToken());
		}
		System.out.println(stair2(N - 1));
	}

    //
    public static int stair2(int n) {
    	//기저사례 : 만약 더이상 내려갈 계단이 없으면 종료. 
    	if(n < 0) { return 0; }
    	if(cache[n] != -1) return cache[n];
    	
    	int ret = 0;
    	//계단을 두개 연속 밟는경우와, 한개 밟고 넘어가는경우
    	if(n >= 0) {
    		//한개 밟고 내려가는 경우
    		int skipStair = stair2(n - 2) + arr[n];
    		ret = Math.max(ret,  skipStair);
    	}
    	if(n - 1 >= 0) {
    		//두개 연속 밟고 내려가는경우(현재 계단과 바로 아래 계단)
    		int onetwoStair = stair2(n - 3) + arr[n-1] + arr[n];
    		ret = Math.max(ret, onetwoStair);
    	}
    	
    	return cache[n] = ret;
    }
    
    //stair(n): n번쟤 계단에서 나머지 [n+1..N]계단을 밟을 떄 최대 점수를 반환한다.
    //마지막 계단은 항상 밟아야 하므로, 
//    public static int stair(int n) {
//    	if(n == N) return 0;
//    	
//    	int ret = 0;
//    	//계단을 밟지않고 넘어가는 경우,
//    	ret = stair(n + 2);
//    	
//    	//현재
//    	for(int i=1; i<=2; i++) {
//    		if(n == -1 || n+i < ) {
//    			ret = start(n + 1) + arr[n+1];
//    		}
//    	}
//    	
//    }
}