[ 백준 - 2579 ] 계단 오르기

난이도 : S3

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

Tag : DP

 

문제 탐색하기 

- 마지막 계단까지 도착했을때 얻을 수 있는 최댓값을 구하여야한다.

- 계단은 한번에 한계단, 두계단씩 오를 수 있다.

- 세개의 계단은 모두 밟아서는 안된다.

시도 1 ( 실패 😓)

떠오른 문제 해결 방법

먼저 테이블은 D[i] = 해당 계단까지 도착했을 때의 최댓값 으로 정의하였습니다.

식은 k = stairs[i-1], stairs[i-2] 중 더 큰값인 계단의 인덱스. D[i] = D[k] + stairs[i] 입니다. 

이유는 i번째의 계단을 오르기 위해서는 연속해서 3계단을 오를 수 없기 때문에 i-1, i-1계단중 하나를 선택해야합니다. 두계단을 모두 선택한다면 i번째 계단을 오를 때 3번연속이기 때문입니다.

 

 

 

 

 

 

시간복잡도⏰

O(N)의 시간복잡도를 가지고 n은 300이하이기 때문에 시간내에도 충분하였습니다.

 

구현 방법 

세부 구현 사항

1. 주어진 값을 입력받는다.

2. i=4부터 점화식을 통해 계산한후 d[i]에 저장한다.

3. i가 목표 n에 도달했을 경우 d[i]를 출력한다.

import java.io.IOException;
import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());// 계단의 개수
        int[] stairs = new int[n];

        for (int i = 0; i < n; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }
        int[] d = new int[n];
        d[0] = stairs[0];
        d[1] = stairs[1] + stairs[0];
        for (int i = 2; i < n; i++) {
            int k = i - 1; // 더 큰 값을 가진 계단의 인덱스
            if (stairs[i - 1] < stairs[i - 2]) {
                k = i - 2;
            }
            d[i] = d[k] + stairs[i];
        }
        System.out.println(d[n - 1]);
    }
}

 

문제는 이렇게 해도 3개의 계단을 선택할 수 있다는 것입니다. 

10, 20, 30, 40 으로 예를들면

40은 20과 30중 더큰 30을 선택했습니다. 하지만 또 30은 10과 20중 20을 선택했었습니다.

결과적으로 20, 30, 40을 모두 선택한것입니다.

 

시도 1 ( 성공 😲)

결국에는 3개를 밟으면 안된다는 조건을 파악해야한다는것입니다. 그렇기 때문에 테이블을 다시 정의했습니다.

d[i][j] = 현재까지 j개의 계단을 연속해서 밟고 i번째 계단에서의 점수합의 최댓값

 

이렇게 하면

 

d[i][0] = stairs[i] + Max(d[i-2][1], d[i-2][0])  // i-2번째 계단을 선택할 경우 연속되지 않음
d[i][1] = stairs[i] + d[i-1][0]  // i-1번째 계단을 선택할 경우 연속됨.

 

즉, d[i][1]의 경우 이미 연속되었기 때문에 무조건 j=0인 상태의 계단을 선택해야합니다.

d[i][0]은 연속되지 않았기 때문에 j=0, j=1이든 상관없습니다.

 

구현 방법 

import java.io.IOException;
import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());// 계단의 개수
        int[] stairs = new int[n + 1];

        for (int i = 0; i < n; i++) {
            stairs[i] = Integer.parseInt(br.readLine());
        }
        int[][] d = new int[n + 1][2];

        d[0][0] = stairs[0];
        d[0][1] = stairs[0];

        d[1][0] = stairs[1];
        d[1][1] = stairs[0] + stairs[1];

        for (int i = 2; i < n; i++) {
            d[i][0] = stairs[i] + Math.max(d[i - 2][0], d[i - 2][1]);
            d[i][1] = stairs[i] + d[i - 1][0];
            // System.out.println(i + ": 0-> " + d[i][0]);
            // System.out.println(i + ": 1-> " + d[i][1]);
        }
        System.out.println(Math.max(d[n - 1][0], d[n - 1][1]));
    }
}

마무리

자주 풀면서 점화식을 구할 수 있도록 하자. 점화식에 대해 여러형태로 고민해보자. 엣지케이스를 생각해보고 안된다면 과감히 다른 방식도 생각해봐야할것같다.