[Java] 2579. 계단 오르기

www.acmicpc.net/problem/2579

2579번: 계단 오르기

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

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

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

 

---

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

public class Main {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args) throws Exception{
		int N = Integer.parseInt(in.readLine());
		int input[] = new int[N + 1];
		int step[] = new int[N + 1];
		for(int i=1; i<=N; i++) {
			input[i] = Integer.parseInt(in.readLine());
		}
		step[1] = input[1];
		if(N >= 2) {
			step[2] = input[1]+input[2];
		}
		for(int i=3; i<=N; i++) {
			step[i] = Math.max(step[i-2], step[i-3]+input[i-1])+ input[i];
		}
		System.out.println(step[N]);
		
	}

}

풀이

실버임에도 불구하고 생각보다 오랜 시간이 걸린 문제였다. (나만 어려웠던듯;;)

우선 Bottom-Up 방식으로 문제를 풀었다.

 

코드를 보면 input과 step 배열이 선언되어 있다.

input : 입력된 계단의 값들을 받아온 배열

step : 그 계단을 올라가기 위한 최적해

 

먼저 DP를 수행하기 전 step[1] 에 input[i]의 값을 넣어준다. 이는 1번째 계단은 1개의 계단만을 올라간 경우만 존재하기 때문이다.

 

다음으로 N>=2 일 경우 step[2]의 경우는 input[1]과 input[2]의 합으로 표현한다. 이는 N이 2 이상이 아닐 수도 있기 때문에 예외처리를 해준 경우이다.

 

그 다음 3번째 계단부터가 이 문제 풀이의 key가 아닐까 싶다.

 

우선 풀이법을 설명하기 전에 필자는 각 계단의 해를 구하는 동시에 직전에 1번 올라간 계단의 수를 저장해서 풀고자 헀었다. 하지만, 이는 51 100 150 100 100의 경우에서 150으로 올라가는 계단에서 250이 최적해이나, 201이라는 값이 나오게 되면서 올바른 풀이법이 아니게 된다. 

 

그래서 다른 방법을 고민하다 결국 다른 사람들의 풀이를 찾아보았다.

 

먼저 step[i] = Math.max(step[i-2], step[i-3]+input[i-1]) + input[i]의 의미를 생각해보아야 한다. 이 코드는 세 개의 계단을 연속해서 밟을 수 없다라는 조건에 의해 이처럼 표현한 것이다.

 

step[i-2] : 2개의 계단을 한번에 올라왔을 경우와 step[i-3]+input[i-1] : 직전 계단에서 올라온 경우인데 step[i-3]을 더해 준 이유는 step[i-1]이 그 당시에 최적해가 될 수는 있다. 하지만 위에 잘못된 풀이법처럼 현재 계단에서는 최적해가 아닐 수 있기 때문에 하나의 계단을 올랐다면, 그 전의 경우는 무조건 2개의 계단을 올라가야 하는 경우여아만 한다.

 

역시 DP는 많이 풀어본다해서 느는게 아닌가보다..