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

오늘은 대표적 DP(Dynamic Programming)문제인 계단오르기를 보겠습니다.

Dynamic Programming 초반에 가장 많이 연습하게 되는 문제인 계단오르기는 처음에 접할때는 조금 어렵습니다..

일단 저는 DP에 대해서 짚고 넘어가야된다고 생각합니다. 

우리는 왜 DP를 사용하는 것에 대해서 정확한 인지가 필요하고 이걸 바탕으로 문제를 풀어보도록하겠습니다.

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

개념이 길긴하지만, 간단하게 쉬운 사례를 들면. 파스칼의 삼각형을 생각해보면 쉬운데 파스칼의 삼각형은 이항계수의 앞의 계수를 구할때 사용하는 방법인데, 이게 삼각형의 모양을 띄고 있다보니, 중복되는 경우가 발생합니다.

그래서 이경우 재귀적(재귀인지 혹은 For문 인지가 정확하지 않아 일단, 재귀적 계산으로 해놓겠습니다.)으로 계산할때 이 중복 계산이 자꾸 시간을 잡아 먹게 되어서 시간 초과가 나는 경우가 발생합니다. 

즉, DP는 중복값이 나올때마다 이미 계산한 값이라면 계산하지 않고 값을 튀어나오는 방식을 차용합니다. 

우리는 이 개념중 가장 큰 것은 이 중복값을 미리 계산해서 그것을 미리 계산 처리 하는 것을 중점으로 두고 문제를 풀어야합니다.

 

이 계단 오르기 문제는 도착 지점으로 가는 경우를 모두 따져볼것입니다.

근데 이 오르기 문제에서 까다로는 지점이 두개가 있는데 

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

이 조건들이 처리하기가 힘들기 때문에 모든 경우를 따져서 해보는 것으로 해보죠, 특히 연속된 세 개의 계단을 밟지 않는 경우가 상당히 까다롭기 때문에 처리를 잘해줘야합니다.

그럼 이걸 풀어가는 방식에 대해서 한번 더 짚고 가겠습니다.

저는 각 계단이 마지막 계단일 경우를 상정하고 모든 가능한 경우를 다 해보겠습니다. 여기서 최대값을 갖는 값은 dp[]로 계단값은 f[n]으로 가정하고 시작하겠습니다.

1. 첫번째 계단이 마지막인 경우 -> 경우는 f[1]입니다.

2. 두번째 계단이 마지막인 경우 -> 경우는 f[1]+f[2] , f[2] 입니다. 단 최대값을 구하는 것이기때문에 아무리 f[1]이 -이 아닌이상 f[2]가 최대값이 되는 경우는 없으므로 f[1]+f[2]이 최대입니다.

3. 3번째 계단이 마지막인 경우 -> 경우는 f[1]+f[3], f[2]+f[3] 입니다. f[1]+f[2]+f[3]은 (연속되서 밟는 경우가 있으므로 안됩니다.) 

이때의 최대값은 f[2]+f[3]이 최대입니다.

4. 4번째 계단이 마지막인 경우 ->  경우는 f[1]+f[2]+f[4], f[2]+f[4], f[1]+f[3]+f[4] 이때 최대값은 f[1]+f[2]+f[4]이고 값은 55입니다. 

여기서부터 이상한 점이 있는데요. 그것이 뭐냐면,

 f[1]+f[2]+f[4], f[2]+f[4], f[1]+f[3]+f[4] 4번째의 계단의 경우의 수부터 중복되는 경우가 있다는 겁니다.

이 빨간 경우는 대부분 2번째 경우의 수의 값을 가지게 되고, 파란 경우는 첫번째 경우에서 파생되서 나온다는 것.

이 빨간 경우에서 최대값은 f[1]+f[2]의 값이 아니었나요?

그러면 굳이 계산할 필요도 없이 dp[2]의 값을 이용하면 되겠죠. -> 이미 우리가 계산을 했으니, 중복된 값을 미리 필요없는 경우 f[2]+f[4]를 계산식에서 애초에 제거를 해주는 셈이 되는거죠.

즉, 빨간 경우는 마지막 도착 지점으로 봤을때  전의 밟은 계단이 3번 연속으로 밟으면 안되니까 한칸 띄어진 거리에서 시작하는 경우라고 생각하면 그 시작지점에서는 갈수 있는 경우의 수가 여러가지 있을테니 그중 최대값과 마지막 발판이 그 값이 되는 것이 됩니다. 

파란 경우는 어떤식으로 생각하면 되냐면, 

마지막 도착 지점으로 부터 연속으로 밟고 도착 한경우라고 생각하면 될 것 같습니다. 그러니까 그 연속으로 출발 해야하기때문에, 그 출발 위치에서 두칸 떨어진 점에서 시작을 해야합니다 .

5. 5번째 계단이 마지막인 경우 ->  f[1]+f[2]+f[4]+f[5], f[2]+f[3]+f[5], f[1]+f[3]+f[5] 이런식으로 경우가 존재할 것인데, 역시 중복되는 경우가 발생하죠?

 f[1]+f[2]+f[4]+f[5], f[2]+f[4]+f[5], f[2]+f[3]+f[5], f[1]+f[3]+f[5]

연두색 경우는 2번째 계단이 마지막인 경우 선택할 수 있는 경우입니다. 근데 최대값은  f[1]+f[2] 값이 최대겠죠?

보라색의 경우는 3번째 계단이 마지막인 경우 선택할 수 있는 경우가 되구요.  이때의 최대값은 f[2]+f[3] 값이 최대일 겁니다. 

그러면 이러한 연속적 추측으로 우리가 생각 해볼 수 있는 껀덕지가 있는데요. 

첫번째는 마지막계단과 그 마지막 계단의 전 계단의 밟는 경우는 마지막 계단수 -3 번째 계단의 수의 최대값의 합을 구할 수  있다는 점.

두번째는 마지막계단을 밟고 마지막계단의 -2 번째 계단의 수의 최대값의 합을 구할 수 있다는 규칙을 어느정도 발견할 수 있다는 것입니다. 

즉, DP문제는 규칙성을 발견하여, 그것을 수식으로 만드는 과정을 잘 해낼 수만 있다면, 문제를 어느정도는 풀 수 있게 됩니다.

이런 규칙성을 가지고 한번 규칙을 만들어보면

cache[n] = Math.max(cache[n-3]+f[n]+f[n-1], cache[n-2]+f[n]);

여기서 cache[]는 그 n번째 계단으로 도착하는 최대값을 가지는 배열입니다.  f[]는 계단이 가지는 숫자들입니다.

이러한 규칙성을 가지고  n값을 찾아 일일히 대입해보면 그 답이 맞게 됩니다.

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

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