[백준/2579/Java] 계단 오르기

 

문제링크:

www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

문제

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

 

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

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

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

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

 

입력

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

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

 

 

출력

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

 

풀이

계단을 오르는 규칙은 3가지가 있습니다.

   3. 마지막 도착 계단은 반드시 밟아야 한다.

그 중 3번째 규칙은 마지막 계단을 밟아야 합니다.

따라서, 마지막 계단 기준으로 규칙을 다시 정리해보겠습니다.

 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

1번 규칙은 2개로 나눌 수 있습니다.

  1-1. 한 번에 한 계단씩 오를 수 있다.

  1-2. 한 번에 두 계단씩 오를 수 있다.

 

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

2번 규칙을 고려해서 마지막 계단(N번째 계단) 기준에서 생각해보면 2가지 케이스가 나옵니다.

 

1-1. N번째 계단은 N-1 계단을 밟고 한 단계 오를 수 있습니다. 그러나 연속 3개는 불가능하므로 N-2를 밟을 수 없습니다. 따라서, N-3 계단에서 2계단 올라와서 N-1을 밟은 다음에 N을 밟을 수 있습니다.

따라서, 점화식은 D[N] = D[N-3] + A[N-1] + A[N] 입니다. (D배열은 최대값, A배열은 계단 점수입니다.)

 

1-2. N번째 계단은 N-2 계단에서 2 단계 오를 수 있습니다.

연속된 계단이 아니므로  N-3, N-2, N도 가능하고 N-4, N-2, N도 가능합니다.

여기서 조금 헷갈릴 수 있는데 N-2 에서 N 계단으로 올라가는 것만 생각하면 됩니다.

N-2 계단은 1-1, 1-2 규칙에 의해 다시 구할 수 있습니다.

따라서, 점화식은 D[N] = D[N-2] + A[N] 입니다. (D배열은 최대값, A배열은 계단 점수입니다.)

 

위 점화식에 D[N-3]이 있으므로 항상 D[N-3]이 존재해야만 합니다.

따라서, D[1], D[2] 값을 미리 설정해놓아야 합니다.

D[1] = A[1] : 첫번째 계단을 밟는 것이 최대값입니다.

D[2] = A[1] + A[2] : 2번째 계단은 1번째, 2번째 계단 모두 밟는 것이 최대입니다.

D[3]은 D[0]는 0이므로 위에서 구한 점화식으로 충분히 계산이 가능합니다.

 

 

 

소스

계단 점수는 A배열에 저장하고, 최대값은 D 배열에 저장합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.io.IOException;

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

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

		for (int i = 1; i <= N; i++) {
			A[i] = Integer.parseInt(br.readLine());
		}

		// 시작점
		D[1] = A[1];

		// 2번째 계단의 최대값은 항상 1번째 계단, 2번째 계단을 밟는 경우입니다.
		if (N >= 2) {
			D[2] = A[1] + A[2];
		}

		for (int i = 3; i <= N; i++) {
			D[i] = Math.max(D[i - 2], D[i - 3] + A[i - 1]) + A[i];
		}

		System.out.println(D[N]);
		
		// D배열 검증
//		System.out.println(Arrays.toString(D));
	}
}