[백준(baekjoon) 2579] 계단 오르기

문제

백준 2579

n개의 계단의 각 점수가 주어진다.
다음과 같은 규칙을 따른 최대 점수를 출력하라.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
   
   • (예를 들어 1번 계단을 밟으면 1 -> 2, 1 -> 3 중 하나만 택할 수 있다.)
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다.
   
   • 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

해결

i 번째 계단에서 가능한 상황은 다음과 같다.

1. X O O (= 연속 2번 밟은 경우)
   
   • 이전 계단에서 첫번째로 밟힌 경우에 자신의 점수를 합산한 것
2. O X O (= 이전은 밟지 않고, 자신이 첫번째로 밟힌 경우)
   
   • 전전 계단이 밟힌 값 중 큰 점수에 자신의 점수를 합산한 것
3. O O X (= 전전, 전을 선택하고 자신은 선택하지 않는 경우)
   
   • 이전 계단에서 2번 연속 밟은 점수와 같음.

즉, 이를 활용해 자신의 차례에서 한번 밟힌 경우와 연속 두번 밟힌 경우를 각각 저장하면 된다.
최종 계단은 무조건 밟아야 하므로 마지막 계단이 밟힌 상황인 1, 2번 값 중 큰 값을 출력한다.

알고리즘

DP로 풀었고, bottom-up 방식이랑 top-down 방식으로 각각 풀었다.

DP에 대해 아직 잘 모른다면 여기의 알고리즘 부분을 보자.

구현 java

1. Bottom-Up 방식

1.import java.util.*;
2.
3.public class Main {
4.    public static void main(String[] args) {
5.        Scanner sc = new Scanner(System.in);
6.        int n = sc.nextInt();
7.        int[][] dp = new int[n][2];
8.        for (int i = 0; i < n; i++) {
9.            int step = sc.nextInt();
10.            dp[i][0] = (i > 1 ? Math.max(dp[i - 2][1], dp[i - 2][0]) : 0) + step;
11.            dp[i][1] = (i > 0 ? dp[i - 1][0] : 0) + step;
12.        }
13.        System.out.println(Math.max(dp[n - 1][0], dp[n - 1][1]));
14.    }
15.}

2. Top-Down 방식

1.import java.util.*;
2.
3.public class Main {
4.    static int[][] dp;
5.    public static void main(String[] args) {
6.        Scanner sc = new Scanner(System.in);
7.        int n = sc.nextInt();
8.        dp = new int[n + 1][2];
9.
10.        for (int i = 1; i <= n; i++) {
11.            dp[i][0] = dp[i][1] = sc.nextInt();
12.        }
13.
14.        goTo(n);
15.        System.out.println(Math.max(dp[n][0], dp[n][1]));
16.    }
17.
18.    static void goTo (int i) {
19.        if (i <= 1) return;
20.        goTo(i - 1);
21.        if (i > 2)
22.            dp[i][0] += Math.max(dp[i - 2][0], dp[i - 2][1]);
23.        dp[i][1] += dp[i - 1][0];
24.    }
25.}

결과

1. Bottom-Up 방식
2. Top-Down 방식