백준 2579 계단 오르기

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

2579번: 계단 오르기

문제

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

<그림 1>

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

<그림 2>

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

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

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

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

시간제한

1초

입력

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

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

 

출력

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

 

풀이

이 문제는 재귀적인 구조를 가지고있다. n번째 계단에 적힌 수를 a(n) 이라 하고, n번째 계단까지 오를 때 밟은 계단의 숫자의 합의 최대값을 f(n)이라 하자. 문제 조건에서 한번에 계단을 한칸 혹은 두칸 오를 수 있다고 했으므로, n번째 계단을 밟기 위해서는 n-1 혹은 n-2 번째 계단을 밟아야만 한다. 따라서, 이 조건만으로 다음 점화식을 도출할 수 있다.

if(n>3) f(n) = max( f{n-1), f(n-2) ) + a(n) , n=1 f(n) = a(n), n=2 f(n) = a(n) + a(n-1) 

이제, 문제의 두번째 조건을 살펴보면, 연속해서 3개 이상의 계단을 밟을 수는 없다고 되어있다. 즉, 위 점화식에서 max( f(n-1), f(n-2) ) = f(n-1) 이고,  f(n-1) = f(n-2) + a(n-1) 이라면, 두번째 조건을 만족하지 못해 틀리게 된다. 

이를 해결하기 위해 한번 더 머리를 써보면, n-1 번째를 밟았다는 것은, n-3 번째 계단을 밟았다는 것이 된다. 첫번째 조건에 의해 n-1번쨰 계단을 밟았다면, n-2 혹은 n-3 번째 계단을 밟아야만하는데, n번째 계단도 밟아야 하므로, 두번째 조건에 의해 n-3 번째 계단을 밟았다는 것이 된다. 따라서 점화식은 다음과같이 변경된다.

if(n>4) f(n) = max( f(n-3) + a(n-1), f(n-2) ) +a(n)
n=1 f(n) = a(n), n=2 f(n) = a(n) + a(n-1),  n=3 f(n) = max( a(1) , a(2) ) + a(3)

이를 코드로 옮기면 다음과 같다.

import java.util.*;

class Main {
	static int a[];
	static int b[];
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		a = new int[n+10];
		b = new int[n+10];
		for(int i=1;i<n+1;i++)
			a[i] = sc.nextInt();
		b[1] = a[1];
		b[2] = a[2]+a[1];
		b[3] = a[2]>a[1]?a[2]+a[3]:a[1]+a[3];
		System.out.println(f(n));
	}
	
	private static int f(int n) {
		if(n>=1 && n<=3)return b[n];
		if(b[n-2]==0)b[n-2] = f(n-2);
		if(b[n-3]==0)b[n-3] = f(n-3);
		return max(b[n-3]+a[n-1],b[n-2])+a[n];
	}
	private static int max(int a,int b) {
		return a>b?a:b;
	}
}