DP - 2579. 계단 오르기

문제

www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

잠깐만

올라가는 방법 말고 내려가는 방법도 생각해보세요

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int inputNum = Integer.parseInt(st.nextToken()); 
		
		int[] values = new int[inputNum+1];		
		for (int i = 1; i <= inputNum; i++) {
			st = new StringTokenizer(br.readLine());
			values[i] = Integer.parseInt(st.nextToken());
			
		}
		
		int[] before1 = new int[inputNum+1];
		before1[inputNum] = values[inputNum];
		
		int[] before2 = new int[inputNum+1];
		before2[inputNum] = values[inputNum];
		
		for (int i = inputNum-1; i >= 0; i--) {
			before1[i] = values[i] + before2[i+1];
			if (inputNum >= i+2) {
				before2[i] = values[i] + Math.max(before1[i+2], before2[i+2]);
			}
		}
		
		int maxBefore1 = Math.max(before1[0], before1[1]);
		int maxBefore2 = Math.max(before2[0], before2[1]);		
		
		System.out.print(Math.max(maxBefore1, maxBefore2));
	}
}

 

설명

올라갈때는 제약이 좀 있습니다.

문제를 다시 읽어보면 시작부분을 제외하고는, 한칸 이동 후 한칸 이동이 불가능해요.

그런데, 시작 부분에서는 가능합니다. 첫번째 계단으로 이동 후, 두번째 계단으로 이동 가능해요

제한조건 등, 설정할 수 있지만, 거꾸로 생각해볼까요?

올라갈때의 목표는 마지막 계단(도착 계단)이잖아요?

그럼 아예 도착 계단부터 내려간다고 생각하면 되잖아요. 그럼 시작 지점은 도착 계단이 되고,

마지막 지점은 달라지겠지만, 케이스를 구분해서 계산하면 되구요.

 

그리고, 연속해서 계단 한칸씩 내려가는건 불가능하니깐,

한번 내려갔을때와 한번에 두칸 내려갔을 때를 나눠서(배열을 나눠서) 계산해요

 

한칸 내려갈때는 두칸 내려간 배열에서 값을 가져오구요.

두칸 내려갈때는 한칸 내려간 배열과 두칸 내려간 배열에서 max값을 가져오구요.

 

제가 임의로 작성한 2,6,7,4,5 계단으로 설명하면 다음과 같습니다.

 

배열[0]과 배열[1], 어느쪽에 도착하더라도 도착 상태이기 때문에 값들을 비교하여 max값을 찾아야 합니다.

before1[0], before1[1], before2[0], before2[1]의 값이 상이한게 보이죠?

max값을 출력하면 됩니다.

 

회고

다음 그림고 같이 처음엔, 두칸 이동과, 세칸 이동(한칸 이동 후 두칸 이동)을 하나의 세트로 생각하여 구현해봤어요.

 

그런게 제가 간과한 부분이 있었습니다.

 

다음 그림 계단처럼 계단의 길이가 짧을때 말이죠

사실 한칸 이동하여 30이 최대값이지만,

두칸 이동과, 세칸 이동(한칸 이동 후 두칸 이동)으로 생각하면 최대값은 20밖에 나올수가 없어요.

 

계단의 길이에 따른 케이스를 분류하여 계산하면 가능도 하겠네요