[알고리즘] 백준 2579 JAVA 자바 계단 오르기 동적프로그래밍

이 문제를 처음에 접했을 때는 어려움이 있었다. 그 이유는 다들 그렇겠지만 규칙 때문이다. 이 규칙이 DP유형이 덜 익숙하게 되면 조건을 걸고 풀어야하는 착각을 하게 된다.

 

DP를 쓰는 이유를 알고 가면 더 쉬워진다. DP는 이미 계산 했던 것들을 계산하지 않고 가져다쓰는 일종의 캐시 개념으로 작동한다. 계산했던것을 몇번이고 다시 계산하면 당연히 느려질 수 밖에 없으니 이를 방지하는 기법이다.

 

그런데 DP를 사용하려면 중요한 점은 규칙을 찾아야 된다는 점이다. 피보나치수열과 같이 뒤로 1, 2번째 값을 더하는 간단한 것들은 바로 머리에 들어오는데 이 문제는 그렇지가 않다. 일단 규칙이 막 있으니까 조건걸어야되나? 싶게 보인다.

 

일단 딱보니 1차원 배열을 이용하면 될 것 같다. 그러면 먼저 1부터 시작해서 가능한 값들을 찾아보면서 시작하면 된다. 

 

dp[] : 최대값 저장 배열

첫 번째 : dp[1]	[1] : stairs[1]
두 번째	[1], [1]+[2]
세 번째	[1]+[2], [2]+[3]
네 번째	[1]+[2]+[4], [2]+[4], [1]+[3]+[4]
다섯 번째	f[2]+f[4]+f[5], f[1]+f[2]+f[4]+f[5], f[2]+f[3]+f[5], f[1]+f[3]+f[5]

이렇게 보면 규칙이 잘 안들어올텐데, 동적 프로그래밍을 생각하고 보면 보인다!

 

 

 

첫번째는 말할 것 없이 [1]이 최대.

 

두번째는 [1] [1]+[2] 두개중 하나 인데 상식적으로 음수가 포함되어 있지않기 때문에 [1]+[2]가 더 클 수 밖에 없다.

 

세번째는 [1]+[2], [2]+[3]둘중 하나인데 이것은 Math.max결정해서 static하게 집어넣으면 된다.

 

이후 네 번째 부터는 반복문을 이용해서 규칙에 따라 집어넣으면 된다.

잘보면 [1], [1]+[2] 이것이 포함되어 있음을 알 수 있는데 이 친구들은 우리가 두 번째에서 계산한 녀석들이다. [1]+[2] 가 더 크기 때문에 dp 집어넣었었다. 이를 통해 한줄기의 빛을 찾았다. 그리고 [1]+[3]+[4]의 경우에는 [1]은 우리가 첫번째 에서 dp[1]에 집어 넣은 녀석이다.

즉 dp[2]의 값과 dp[1]의 값이 어떤 규칙에 의해서 들어간다는 건데...

자세히보면 [4]의 앞 값을 보면 알 수 있다. dp[2]의 값을 요구하는 dp[4]는 [3]이 없고 dp[1]의 값을 요구하는 dp[4]는 [3]이 존재한다. 즉 더블로 점프해서 왔느냐 아니면 연속적으로 왔느냐 이걸 보면 알 수 있다.

 

여기에서! 우리는 둘중 최대값을 선택해서 dp[4]에 넣어야된다.

그럼 규칙을 대충 쓰면

연속적으로 왔을 때 : dp[i - 3] + stairs[i - 1];
점프해서 왔을 때 = dp[i - 2];

 

이 규칙이 5번째에도 적용이 되는지 보면 실제로 잘 적용이 된다.

 

 

 

public class BaekJoon_16_2579 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(reader.readLine());

		int[] stairs = new int[301]; 
		int[] dp = new int[301];

		for (int i = 1; i <= n; i++) {
			stairs[i] = Integer.parseInt(reader.readLine());
		}

		dp[1] = stairs[1];
		dp[2] = stairs[1] + stairs[2];
		dp[3] = Math.max(stairs[1] + stairs[3], stairs[2] + stairs[3]);
		for (int i = 4; i <= n; i++) {
			int stepbystep = dp[i - 3] + stairs[i - 1];
			int doublestep = dp[i - 2];

			dp[i] = stairs[i] + Math.max(stepbystep, doublestep);
		}

		writer.write(dp[n] + "");

		writer.flush();
		reader.close();
		writer.close();
	}

}