[JAVA/백준2579] 계단오르기 - DP

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

2579번: 계단 오르기

1. 문제

2. 풀이

이 문제는 처음 접근했을때 생각을 잘못해서 고민하는 시간이 굉장히 오래 걸렸다.

마지막에서 결국 정답에 근접한 규칙을 알아냈지만 이를 점화식으로 이끌어내는것이 쉽지 않았고, 결국 여러 힌트를 얻어낸 뒤에 풀 수 있었다. 

 

처음에는 3가지 규칙에 근거하여 출발점으로 부터 한칸 또는 두칸씩 계단을 올라가면서 누적된값을 비교해서 최대값이 나오는 경우의 위치에서 다시 계단을 올라가는 방식으로 생각을 해보았다.

하지만 이 경우의 반례는 예시로 출발 10 20 60 40 에서 60까지 누적된 값은 10+60=70과 20+60=80으로 후자의 경우가 최대값이다. 하지만 여기서 후자를 선택할 경우 마지막 도착 계단을 밟아야하는데 이때 3번 연속 계단을 밟게되므로 규칙에 어긋나게 된다. 반드시 생각할 것은 세가지 규칙을 만족하는 프로그램 로직을 설계해야만 원하는 결과가 나오기 때문에 세가지 규칙을 지키면서 규칙적으로 동작하는 점화식을 세우는것이 중요하다.

 

각 계단의 점수에 집중하기 보다는 위 문제에서 제시한 규칙에 근거하여 여러 테스트케이스를 만들어가다 보면 결국 규칙을 찾을 수 있다. 도착점에 오기 전, 출발점이 도착점의 전 위치인지 혹은 도착점의 전전 위치인지에 따라서 계단을 한칸 혹은 두칸으로 오를 수 있는 경우가 다르게 된다.

 

i번째 계단에 도착할 경우 점수의 최대값을 구한다고 가정하자.

 

1) 시작점이 i번째 계단 전 위치(i-1번째)일 경우   

i-1번째에서 오는 경우 연속된 세개의 계단을 밟으면 안되므로 (i-3번째)→(i-1번째)→i번째 순서로 가게된다.

따라서, i번째 누적값 = i-3번째 누적값 + i-1번째 누적값 + i번째 계단의 점수

 

2) 시작점이 i번째 계단 전전 위치(i-2번째)일 경우

i-2번째에서 오는 경우 계단을 두번 밟고 올라가야 규칙을 지키면서 i번째에 도착할 수 있다.

따라서, i번째 누적값 = i-2번째 누적값 + i번째 계단의 점수

 

위 1,2번 규칙은 계단이 3개이상일경우 부터 적용된다.

 

3. 소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.valueOf(bf.readLine()); // 계단 개수
		int[] f = new int[n+1];//계단 배열
		int[] sum = new int[n+1]; //누적값 저장
		f[0]=0;//출발점
		
		for(int i=1; i<f.length; i++) {
			f[i]=Integer.valueOf(bf.readLine());
		}
		
		//예외
		sum[1]=f[1];
		sum[2]=f[1]+f[2];
		
		//n>=3부터
		for(int i=3; i<=n; i++) {
			//마지막 전(i-1)일경우와 마지막 전전(i-2)일 경우 비교
			sum[i]=Math.max(sum[i-3]+f[i-1]+f[i],sum[i-2]+f[i]);
		}
		System.out.println(sum[n]);
	}
}