[BOJ] 2579: 계단 오르기(JAVA)

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

2579번: 계단 오르기

문제

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

<그림 1>

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

<그림 2>

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

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

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

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

입력

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

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

출력

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

예제 입력 1 

6

10

20

15

25

10

20

예제 출력 1 

75

 

---

[문제 풀이]

1. 입력받은 계단의 수 n이 1인 경우, 해당 계단을 밟는 것이 최대이므로 stage[0]을 반환하고 종료

2. 입력받은 계단의 수 n이 2인 경우, 모든 계단을 밟는 것이 최대이므로 stage[0]+stage[1]을 반환하고 종료

3. 입력받은 계단의 수 n이 3 이상인 경우, 정수 배열 sum에 최댓값을 계산한다.

    3-1. 마지막 계단은 반드시 밟아야 하므로 마지막 계단에서 내려오는 방식으로 최댓값을 계산해 줄 것이다. 따라서 sum[n-1] = stage[n-1] 값을 넣어준다.

    3-2. stage[n-2]를 밟을 수 있는 경우의 수 중 최대는 마지막 계단을 밟고 해당 계단을 밟는 것이므로 sum[n-2] = stage[n-2] + sum[n-1]

    3-3. stage[n-3]을 밟을 수 있는 경우의 수 중 최대는 마지막 계단을 밟고 해당 계단을 밟는 것이므로 sum[n-3] = stage[n-3]+sum[n-1]이다. 연속으로 밟을 수 있는 계단의 수는 2개이므로, 모든 계단을 다 밟고 해당 계단을 밟는 경우는 연속으로 밟는 계단의 수가 3개이므로 규칙에 어긋나므로 최댓값으로 치면 안된다.

     3-4. 위처럼 경우의 수가 1가지인 경우의 sum값을 초기화시키고 그에 해당되지 않는 계단은 다음과 같이 계산한다.

           3-4-1. 해당 계단을 밟는 경우의 수는 두 가지가 있다. 현재 밟아야 할 계단이 3번째 계단이라면,

                    1) 5번째 계단을 밟고 내려온 최댓값에 현재 밟을 계단의 값을 더해준 값과, 

                    2) 6번째 계단을 밟고 내려온 최댓값에 4번째 계단의 값과 현재 밟을 계단의 값을 더해준 값

                    두가지가 존재할 수 있고 이 두 값 중에서 더 큰 값을 sum[3]에 저장해주면 된다.

                    for(int i=n-4;i>=0;i--) 
                         sum[i] = stage[i] + Math.max(sum[i+2], sum[i+3]+stage[i+1]);

           3-4-2. 모든 계단에 최댓값을 저장한 sum배열이 완성되면 sum[0]과 sum[1]을 비교해 최댓값을 반환해주면 된다. 그 이유는 연속된 두개의 계단만 밟을 수 있으므로 처음으로 밟는 계단이 0번째 계단인지 1번째 계단인지에 따라 최댓값이 또 달라지기 때문이다.

 

[코드]

import java.util.*;

public class Main {

    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
     	int n = sc.nextInt();
    	int[] stage = new int[n];
    	int[] sum = new int[n];
     	for(int i=0;i<n;i++)
          stage[i] = sc.nextInt();
    
     	int count=1;
        sum[n-1] = stage[n-1];
    
     	if(n==1)
          System.out.println(sum[0]);
    
     	else if(n>2) {
          sum[n-2] = stage[n-2]+stage[n-1];
          sum[n-3] = stage[n-3]+stage[n-1];
    
          for(int i=n-4;i>=0;i--) 
               sum[i] = stage[i] + Math.max(sum[i+2], sum[i+3]+stage[i+1]);
     
          System.out.println(Math.max(sum[0],sum[1]));
     	}
     	else 
          System.out.println(stage[0]+stage[1]);
   
    }
}