2579번 : 계단 오르기 ( 백준 / java )

www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

 

*해결과정

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

 

이 부분이 가장 핵심적이라고 생각한다. 처음에는 건널 수 있는 계단 조합을 생각해서

212칸 이동 + 121칸 이동

12칸 이동 / 21칸 이동 / 2칸 이동

등등 어떻게 하면 모두를 만족시키면서 dp를 최대값으로 계속 추가할 수 있는지 고민하였다. 하지만 접근 방법이 잘못되었다. 계속 최선의 계단의 점수로 업데이트를 하는 것은 규칙을 충족하려는 것에 너무 신경을 쓴 것이다. 조건을 충족하면서 dp에 저장된 값을 적극 활용해야 한다. 또한 우리는 마지막 계단을 밟아야하므로 dp[N]에 초점을 맞추고 규칙을 새운다. 규칙에 맞게 이동할 수 있는 조건을 2가지이다.

 

n-3계단	n-2계단	n-1계단	n번 째 계단(현재 계단)
O	X	O	O
O or X	O	X	O

첫번째 케이스는 21칸 이동

두번째 케이스는 2칸 이동

 

처음에 이 2가지를 활용하면 212칸, 221칸 등의 조합이 나오지만 2112, 2211등의 조합은 나올 수 없지 않을까라는 생각이 들었다. 하지만 이 역시 아직도 문제 해결 방법을 제대로 파악하지 못한 것이다. 몇 칸의 조합으로 건너뛰든지 dp에 계속 갱신하기 떄문에 조건2만 신경쓰면 된다.

 

따라서 핵심은 계속 2칸만 이동하는 것은 상관없지만 21칸 이동은 연속으로 2계단을 올라가기 때문에 다음에는 무조건 2계단을 건너 뛰어야 한다. 따라서 첫번째 케이스, 두번째 케이스 모두 이전의 최선의 dp값에서 무조건 2칸을 건너뛰면서 시작한다. 이 설명이 이해되지 않는다면 [1,100,50,50,30,20] 의 계단을 그려보고 직접 해본 후 다시 읽어보기 바란다.

 

 

package bj;

import java.util.*;
public class bj_2579_DP {

	static int N;
	static int[] array;
	static int[] dp;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		array= new int[N+1];
		dp = new int[N+1];
		
		for(int i=1;i<=N;i++) {
			array[i] = sc.nextInt();
		}
		
		dp[1] = array[1];
		if(N==1) {
			System.out.println(dp[N]);
			return;
		}
		dp[2] = array[1]+array[2];
		if(N<=2) {
			System.out.println(dp[N]);
			return;
		}
		
		for(int i=3;i<=N;i++) {
			dp[i] = Math.max(dp[i-2]+array[i], dp[i-3]+array[i-1]+array[i]);
		}
		System.out.println(dp[N]);
	}

}

 

dp는 항상 어렵다... dp를 더 많이 풀어보고 조건들을 확인하여 식을 세워보자!