[백준 - Java] 2579번 : 계단 오르기

문제

www.acmicpc.net/problem/2579

2579번: 계단 오르기

설명

(Dynamic Programing) 동적 계획법으로 풀 수 있는 문제다.

DP를 푸는 방식은 크게 Top-Down과 Bottom-UP 방식으로 나뉘는데 Bottom-Up방식으로 구현할 것이다.

Bottom-Up 방식은 작은문제부터 풀어가며 전체 문제를 풀어가는 방식이다. 이 방법은 대개 반복문을 통해 구현된다.

 

먼저 계단을 오르는 규칙에 대해 알아보자.

계단을 오르는 규칙

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

따라서 첫 번째 계단을 밟고 두 번째 계단 또는 세 번째 계단 중 한 계단으로 오를 수 있다.

하지만, 첫 번째 계단을 밟고 3칸을 점프해 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

 

이를 잘생각해보면 현재 계단이 i일 때

1. 그 전 계단 i-1을 밟고 올라왔는지

2. 아니면 그 전전 계단 i-2에서 점프해서 왔는지로 나눠서 계산한다.

(계단을 밟는 개수는 최소가 되어야 하므로 전 단계 i-1을 밟았으면 그 전전 단계 i-2는 점프했다고 가정한다.)

 

1. 전 계단 i-1을 밟고 올라왔을 경우

현재 계단까지의 최대값 dp [i]는

전 단계 steps[i-1]과 점프 전 최대값 dp [i-3]의 합에 현재 계단의 값 steps[i]을 더한 값이다.

 

2. 만약 전 단계 i-1을 밟지않고 i-2에서 점프했다면

현재 계단까지의 최대값 dp [i]는

점프한 최댓값 dp [i-2]와 현재 계단의 값 steps [i]를 더한 값이다.

 

이 둘 중 큰 값을 dp [i]에 저장하면 된다.

 

* 계단은 1~N번 인덱스까지 있고, 0번 인덱스는 시작 계단으로 둔다.

 

* dp는 계단을 2칸 점프할 수 있는 3번 인덱스 계단부터 시작한다.

따라서 i-3의 연산에서 3 미만의 계단은 음수로 ArrayIndexOutOfBoundsException 에러가 날 수 있기에

첫 번째 계단과 두 번째 계단은 미리 계단에 쓰인 값으로 초기화해주고 dp를 시작한다.

전체 코드

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		int[] stairs = new int[N+1];

		for(int i = 1; i < N+1; i++) {
			stairs[i] = sc.nextInt();
		}

		int[] dp = new int[N+1];
		dp[1] = stairs[1]; // 첫번째 계단 dp 초기값으로 초기화 
		if (N >= 2) { // N = 1의 경우가 있을 수 있기 때문에 예외처리
			dp[2] = stairs[1] + stairs[2]; // 두 칸 점프를 할 수 있는 3번째 계단부터 시작하기 때문에, 2번째 계단 역시 초기화 
		}
		
		for(int i = 3; i < N+1; i++) {
			dp[i] = Math.max(dp[i-2], dp[i-3] + stairs[i-1]) + stairs[i];
		}

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

}

GITHUB

github.com/KwonMinha/BOJ/blob/master/BOJ%232579/src/Main.java

KwonMinha/BOJ

참고

[백준] 2579번 : 계단 오르기 - JAVA [자바]

https://geehye.github.io/baekjoon-2579/#