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

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.

각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

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

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다.

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

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

입력

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

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다.

계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

문제해결방법

2번 조건에 의해 연속된 세 개의 계단을 모두 밟으면 안되기 때문에 한 계단 오르고 한 계단 오르면 세 개의 계단을 밟게 된다.

따라서 N번 계단에 올라오기 위해서는 N-1번 계단을 두 계단으로 올라오고 한 계단으로 올라오거나

N-2번 계단에서 두 계단으로 올라와야 한다.(이때, N-2번 계단으로 올라오는 방법은 상관없다.)

위 내용을 식으로 표현하면 아래와 같다.

- 한 계단으로 올라온 N번 계단 점수 = 두 계단으로 올라온 N-1계단 점수 + N번 계단 점수

- 두 계단으로 올라온 N번 계단 점수 = Max(한 계단으로 올라온 N-1계단 점수, 두 계단으로 올라온 N-1계단 점수) + N번 계단 점수

(N번 계단에 한 계단으로 올라오는 것과 두 계단으로 올라오는 두 가지 방법을 계산하기 위해 2차 배열을 사용한다.)

코드

package blogQueue;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main2579_계단오르기 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] stairs = new int[n+1];
        for(int i=1; i<=n; i++) stairs[i] = Integer.parseInt(br.readLine());
        int[][] scores = new int[2][n+1];
        scores[0][1] = stairs[1];
        scores[1][1] = stairs[1];
        for(int i=2; i<=n; i++) {
            scores[0][i] = scores[1][i-1] + stairs[i];
            scores[1][i] = Math.max(scores[0][i-2],scores[1][i-2]) + stairs[i];
        }
        System.out.println(Math.max(scores[0][n], scores[1][n]));
    }
}
 

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.