[백준 알고리즘] 2597번(계단 오르기) - DP 문제

백준 알고리즘

DP 문제를 마스터하기 위해 오늘도 DP 문제를 풉니다.

이 계단 오르기 문제는 제약사항이 있습니다. 

아래에 문제를 보시면 아시겠지만 제약 조건이 있기 때문에 그 조건에 맞춰서

마지막부터 고려하여 식을 작성하면 될 것 같습니다.

  문제

  해석

일단 문제를 이해하시는데 큰 어려움은 없을 것이고, 조건이 무엇인지 보겠습니다.

1. 한 번에 1계단 또는 2계단 오를수 있다.

2. 연속된 3계단을 오르지 못한다.

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

다음은 예제 입력을 배열로 나타낸 것입니다

여기서 list[1] > list[2] > list[3] 이렇게 연속해서 밟으면 안되며 마지막 list[6]은 무조건 밟아야 합니다.

맨 뒤에 list[6]을 밟아야 하니 마지막부터 보겠습니다.

도착점을 밟을 수 있는 경우 수를 한번 찾아보겠습니다.

아래는 도착점을 밟을 수 있는 방법 두 가지 입니다.

             

왼쪽의 경우 : 도착점(list[6]) / 도착점 - 1(list[5]) 

오른쪽의 경우 : 도착점(list[6] / 도착점 - 2(list[4])

제 2의 규칙으로 인해 왼쪽의 경우 list[4]는 밟으면 안됩니다. 오른쪽의 경우 list[4]를 밟았으면 list[5]는 밟으면 안되는 것입니다.

그 전에 어떤 것을 밟았던지 결국에는 이 2가지 경우 밖에 생기지 않습니다. 

그래서 우리는 여기서 list[6]에 도착했을 경우 최댓값을 구하는 것 입니다.

그러면 여기에서 최댓값을 result 배열을 만들어 저장하도록 하겠습니다. 

즉, result[i] = i 번째 최댓값 이 될겁니다.

이제 우리는 2의 규칙을 넣어야합니다. 그래서 2차원 배열을 한번 사용해보겠습니다.

사실 1차원 배열을 하나 더 사용해도 됩니다. 

result[i][0] = i 번째 계단을 1칸 전에 (위의 왼쪽 그림)     /    result[i][1] = i 번째 계단을 2칸 전에 (위의 오른쪽 그림)

그림이 너무 헷갈리겠지만 천천히 읽어보시면 이해가 되실 겁니다.

이 경우 i 계단에서 최댓값을 구할 경우 1계단 전에 밟아야 하는 경우 입니다.

그래서 보라색 숫자는 도착점 1칸 전에 반드시 밟아야 하는 계단입니다.

보라색 숫자를 밟기 전에 밟을 수 있는 계단은 하늘색으로 표시를 해두었습니다.

하지만 규칙에 의해서 당연히 list[4] 하늘색은 밟지를 못합니다. 

그렇다면 list[5]에서 내려다 봤을 때 그 전에 반드시 2칸 전에서 올라오는 경우만 가능하다는 것을 알 수 있습니다.

이것을 점화식으로 나타내보겠습니다.

result[i][0] = result[i-1][1] + list[i] 

result[i][1]은 2칸 전에 올라오는 경우의 값을 저장하는 곳이기에 현재 i 까지의 최댓값과 i의 값을 더해주면 그 값을 구할 수 있습니다.

그 다음 경우를 보겠습니다.

이 경우 i 계단에서 최댓값을 구할 경우 2계단 전에 밟아야 하는 경우입니다.

그래서 보라색 숫자는 도착점 2칸 전에 반드시 밟아야 하는 계단입니다.

보라색 숫자를 밟기 전에 밟을 수 있는 계단은 하늘색으로 표시를 해뒀습니다.

list[2] > list[4]이 경우와 list[3] > list[4]이 경우 2가지가 있습니다.

우리는 최댓값을 구해야하기 때문에 두 수의 합을 구해서 비교해봐야 합니다.

이것을 점화식으로 나타내겠습니다.

result[i][1] = max(result[i-2][1], result[i-2][0]) + list[i]

이렇게 되겠습니다. i일 때 각 최댓값이 저장되는 곳은 result 배열이니 이 곳에서 각각의 최댓값을 가지고 오게됩니다.

이제 이것을 이용하여 코딩을 하면 되겠습니다.

코드를 보시면 각 배열에 값이 어떻게 저장이 되는지 확인하는 구문이 있습니다.

그것으로 각 배열에 어떤 값이 들어가는지 확인하면서 돌려보시면 될 것 같습니다.

이해하시는데 조금 도움이 될 것이라 생각합니다.

  코드

import java.util.Scanner;
 
import javax.swing.plaf.synth.SynthSpinnerUI;
 
public class Beak2579 {
 
    static int[] list;
    static int[][] result;
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
 
        list = new int[n+1];
        result = new int[n+1][2];
        for (int i = 1; i <= n; i++) {
            list[i] = sc.nextInt();
 
        }
        result[1][0] = result[1][1] = list[1];
        for (int i = 2; i <= n; i++) {
            result[i][0] = result[i - 1][1] + list[i];
            result[i][1] = Math.max(result[i - 2][0], result[i - 2][1]) + list[i];
            
            //System.out.println(result[i][0]+ " "+ result[i][1]);
        }
 
        System.out.println(Math.max(result[n][0], result[n][1]));
    }
}