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

문제

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

풀이

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

위 세 가지 조건을 고려하여 총 N개의 계단을 쪼개 '각 계단이 마지막 계단일 경우 현재 계단 까지의 최고 점수'를 DP테이블 값으로 지정해 1~n위치 까지 최고 점수를 차례대로 구한다. (Bottom-Up 방식)

이를 위해서 '마지막으로 n번째 계단을 밟는 경우'를 구해보자.
우선 '계단은 한 번에 한 계단씩 혹은 두 계단씩 오를 수 있다'는 첫번째 규칙에 의해 n-1을 밟고 오는 경우 / n-2를 밟고 오는 경우 2가지가 존재하다.

 

그런데 여기서 '연속된 세 개의 계단을 모두 밟아서는 안 된다.'는 두번째 규칙에 의해 'n-1을 밟고 오는 경우'에 제한이 걸리게 된다. n-1을 밟고 바로 n을 밟기 위해서는 이전에 n-2를 밟지 않고, n-3을 밟고 와야 한다는 제한이 생긴다. (n-2 → n-1 경로로 오면 그 다음 n을 밟을 수 없게 됨) 그러면 두 경우는 결국 아래로 정해진다.

 

계단 n까지의 최고 점수 = '계단 n까지 오는 경우 중 최고 점수' + 계단 n의 점수
int[] dp : 1~n 각 계단에 대한 '현재 계단(n)까지의 최고 점수'
int[] stair : 각 계단의 점수

dp[n] = Math.max(dp[n-3] + stair[n-1], dp[n-2]) + stair[n]

 

코드

import java.util.Scanner;

// 계단 오르기
public class Ex_2579 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // 각 계단 점수
        int[] stair = new int[n + 2];
        for (int i = 1; i <= n; i++) {
            stair[i] = sc.nextInt();
        }

        // 해당 계단 위치까지의 최고 점수
        int[] score = new int[n + 2];
        score[1] = stair[1];
        score[2] = stair[1] + stair[2];
        for (int i = 3; i <= n; i++) {
            score[i] = Math.max(score[i - 3] + stair[i - 1], score[i - 2]) + stair[i];
        }

        System.out.println(score[n]);
    }
}

 

• 시작 위치에서 첫 번째, 두 번째 계단은 n-3 계단 값이 존재하지 않기 때문에 별도로 지정
  세 번째 계단은 시작위치(stair[0] = 0) 값을 n-3으로 사용할 수 있기 때문에 반복문에 포함시켜도 괜찮다.
• 배열 크기가 n+2인 이유는 입력 값 N이 1일 경우(계단이 1개 존재), score[2] = stair[1] + stair[2] 에서 인덱스가 배열 크기를 넘어가 ArrayIndexOutOfBoundsException 예외가 발생하는 걸 방지하기 위함이다. (최소한으로 인덱스가 0, 1, 2는 존재하도록)

★ DP문제를 풀 때는 각 경우들에 대해 '해당 경우로 올 수 있는 경우'들을 파악한 뒤, '해당 요소가 마지막일 경우의 ~값'을 DP테이블로 설정해서 메모이제이션 하는 식으로 풀이한다.