[백준] 2579 계단오르기

1. 문제

www.acmicpc.net/problem/2579

2579번: 계단 오르기

2. 접근방법

계단을 올라가되 한 칸 또는 두 칸을 올라 갈 수 있고

연속해서 3계단을 오를 수는 없다.

이 때 가장 마지막 계단에 도착했을때 점수를 가장 높게 받는 경우를 찾는 문제

 

간단한 dp문제이다.

 

 

내가 끌어낸 점화식은

1번 계단 까지 최대 점수는 1번 자신 10점

2번 계단 까지 최대 점수는 1번 + 2번 30점

3번 계단 가지 최대 점수는 1번+3번 or 2번+3번 중 높은 점수 35

까지는 동일하고

 

4번 계단 부터 생각해봤을때

4번 계단으로 올라가는 방법은

2번에서 두칸 올라가기

3번에서 한칸 올라가기

 

두가지 방법 뿐이다.

여기서 3번에서 한칸 올라가기 위해서는 2번은 반드시 들리지 않은 상태여야 한다. (연속 3계단 ㄴㄴ)

 

즉

1번까지 최대 값 -> 3번 -> 4번 과

2번까지 최대 값 -> 4번 

 

두 경우를 비교해 더 큰값이 4번까지의 최댓값이 되는 것이다.

코드로 보면

i는 현재 계단의 위치

num이 현재 계단의 값

pre가 이전 계단의 값

dp는 해당 계단의 최댓값

 

max(dp[i-2] + num , dp[i-3] + pre + num) 가 현재 계단의 최댓값이 되겠다.

 

주의) N이 3이하인 경우 점화식을 이끌어내기 전에 결과가 정해지니 조심하자

3. 자바 코드

package Silver;

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

public class P2579계단오르기 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		int dp[] = new int[N + 1];
		dp[0] = 0;
		dp[1] = Integer.parseInt(br.readLine());
		int pre = 0;
		if (N != 1) {
			pre = Integer.parseInt(br.readLine());
			dp[2] = dp[1] + pre;
		}
		for (int i = 3; i <= N; i++) {
			int num = Integer.parseInt(br.readLine());
			dp[i] = Math.max(num + dp[i - 2], num + pre + dp[i - 3]);

			pre = num;
		}
		System.out.println(dp[N]);
	}

}

4. 마치며

N의 값이 엄청나게 커진대도 현재 위치에서 -3 한 위치까지만 값이 필요하니

슬라이딩 윈도우로 dp의 크기를 고정시킬 수 있을 것 같다.

하지만 여기서는 필요하지 않으니 패쓰