[백준] 2579번 : 계단 오르기

2579번: 계단 오르기

# 문제

 

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

 

계단 오르는 데는 다음과 같은 규칙이 있다.

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

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

 

# 입력

 

입력의 첫째 줄에 계단의 개수가 주어진다.

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

 

# 출력

 

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

# 예제 입력

6
10
20
15
25
10
20

# 예제 출력

75

---

동적 프로그래밍 문제이다. 입력을 받을 배열 stairs[]와 각 계단이 가질 수 있는 최대 값을 저장할 배열 arr[] 총 2개의 배열이 필요하다. 동적 프로그래밍 문제는 복잡하더라도 멀리서 넓게보고 접근하는 것이 필요한 것 같다. 자칫 Greedy로 접근하게 되어 시간을 버리는 경우를 종종 경험했기 때문이다. 멀리서 보지 않고 가까이서 최적해를 찾아나가면 그것이 Greedy이다.

 

풀고나니 굉장히 간결한 코드로 작성할 수 있는 것을 괜히 시간낭비 했었다ㅠ..

 

예제의 입력대로 6 10 20 15 25 10 20를 입력하면 6개의 계단이 있고,

1번 계단은 10점

2번 계단은 20점

3번 계단은 15점

...

마지막 6번 계단은 20점을 갖는다.

 

문제의 조건은 세 개의 계단을 연속으로 오를 수 없다 했으니 굉장히 큰 제약이 생긴 것 같다. 그리고 마지막 계단은 반드시 밟아야하므로 Top-Down으로도 접근해보았으나 역시 Bottom-Up이 더 쉽다.

 

stairs[] = [0, 10, 20, 15, 25, 10, 20] 일 때 arr[]를 구해보자. arr은 i번 째 계단이 갖을 수 있는 최대 값임을 기억하자.

arr[1] = stairs[1];

arr[2] = stair[2] + stairs[1];

 

arr[3]은 stairs[1]에서 stairs[2]를 건너뛰고 올 수도 있고, stairs[1]을 건너뛰고 stairs[2]를 밟고 올 수도 있으므로

arr[3] = Math.max(stairs[1], stairs[2]) + stairs[3];

 

arr[4]부터는 조금 접근하기 어려울 수 있다.

1번-2번-4번,

1번-3번-4번,

2번-4번의 경우가 있다.

마치 경우의 수가 3개인 것 처럼 보이지만 실제론 그렇지 않다. 1번-2번-4번과 2번-4번은 한 가지의 경우로 볼 수 있다.

arr[4] = stairs[1] + stairs[2] + stairs[4]

arr[4] = stairs[2] + stairs[4] 가 될 수 있는데, 문제에서 찾는 값은 최대 값이므로 arr[4] = arr[2] + stairs[4]로 표현 할 수 있다.

 

따라서 arr[4] = Math.max(arr[1] + stairs[3], arr[2]) + stairs[4] 이다.

이를 점화식으로 보면 arr[i] = Math.max(arr[i-3] + stairs[i-1], arr[i-2]) + stairs[i] 인 셈이다.

 

# Whole Code </>

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n < 1 || n > 300) System.exit(0);

        int[] stairs = new int[n+1];

        for(int i=1; i<=n; i++){
            stairs[i] = sc.nextInt();
            if(stairs[i] > 10000 || stairs[i] < 1)System.exit(0);
        }
        System.out.printf("%d\n", getMaxScore(stairs, n));
    }

    private static int getMaxScore(int[] stairs, int n) {

        int[] arr = new int[n+1];

        arr[1] = stairs[1];
        if(n > 1) arr[2] = stairs[1] + stairs[2];
        if(n > 2) arr[3] = Math.max(stairs[1], stairs[2]) + stairs[3];

        if(n > 3)
            for(int i=4; i<=n; i++)
                arr[i] = Math.max( arr[i-3] + stairs[i-1], arr[i-2] ) + stairs[i];

        return arr[n];
    }
}