[BOJ/백준] 2597 계단 오르기(JAVA)

링크

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

 

문제 요약

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총점수의 최댓값 구하기

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

 

제한

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

풀이

주어진 예제에 대해 최대 점수로 각 계단에 도착하는 방식은 아래와 같습니다.

도착 계단	1번	2번	3번	4번	5번	6번
경로	1	1-2	2-3	1-2-4	1-2-4-5	1-2-4-6
점수	10	10+20	20+15	10+20+25	10+20+25+10	10+20+25+20

처음 봤을 때 가능한 경로를 다음과 같이 정리해 봤습니다.

• 1번: 항상 1
• 2번: 항상 1-2
• 3번: 1-2-3(2번 점수>1번 점수일 때) / 1-3(1번 점수>2번 점수일 때)
  • ⇒ (1,2번 중 점수가 큰 쪽) + 3번 점수
• 4번: 1-2-4(2번 점수>3번 점수일 때) / 1-3-4(3번 점수>2번 점수일 때)
  • ⇒ (2,3번 중 점수가 큰 루트) + 4번 점수
• ...

 

1번과 2번은 항상 경로가 같으므로 초기값을 지정할 수 있습니다.

그 이외의 숫자 N까지의 경로는 (N-1, N-2번 중 점수가 큰 쪽 루트) + N번 점수라고 정리했습니다.

 

하지만 이는 잘못된 정리입니다!!

 

3번까지의 루트를 봅시다.

1번과 2번 중 2번의 점수가 더 크므로 2번까지의 루트 + 3번을 선택하게 됩니다.

근데, 이렇게 되면 루트가 1-2-3이므로 연속된 세 개의 계단을 밟으면 안 된다는 규칙을 어기게 됩니다.

 

⇒ N번까지의 루트를 정할 때 N-1번 루트를 가져다 쓰면, 연속된 세 개의 계단을 밟았는지 고려할 수 없습니다.

 

 

N번째 계단에 오기 직전을 생각해 봅시다. 총 두 가지 경우가 발생할 수 있습니다.

1. `N-2`번째 계단 도착하고, N번째 계단 밟기(두 계단 오름)
2. N-3번째 계단 도착하고, N-1번째 계단을 밟고, N번째 계단 밟기(한 계단 오름)

 

2번째 경우는 3 계단을 연속으로 밟지 않기 위해 N-3번째까지 고려해야 합니다.

결론적으로, 저 두 경우 중 점수 합이 큰 루트를 선택하면 됩니다!

 

두 경우로 나눠 경로를 다시 정리하면 다음과 같습니다.

• 1번: 항상 1
• 2번: 항상 1-2
• 3번: 2-3(1번 루트+3번) / 1-3(시작점+1번+3번)
• 4번: 1-2-4(2번 루트+4번) / 1-3-4(1번 루트+3번+4번)
• 5번: 1-2-4-5(4번 루트+5번) / (3번 루트+4번+5번)
• ...

 

코드

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

public class Main {

    static int N;
    static int[] dp;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        dp = new int[N + 1];
        arr = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        dp[1] = arr[1];
        System.out.print(sol(N));
    }

    // N번 계단 도착 = ((N-2번 계단 밟기) or (N-3번과 N-1번 계단 밟기)) + N번 계단 밟기
    static int sol(int num) {
        if(dp[num] > 0){ // 이미 계산된 경우
            return dp[num];
        }

        if(num <= 1){
            return dp[num];
        }

        if (num == 2) { // 2번 계단은 항상 1번 계단 + 2번 계단
            return dp[2] = arr[1] + arr[2];
        }

        return dp[num] = Math.max(sol(num - 2), sol(num - 3) + arr[num - 1]) + arr[num];
    }
}

🏷 시간 복잡도

• 각 N개의 계단에 대해 최대 점수를 한 번씩만 계산하므로 시간 복잡도는 O(N)

🏷 실행 속도

Time: 100 ms, Memory: 14224 KB