[JAVA] BOJ 2579 계단 오르기

 

 

계단 오르기 문제는 정답 비율이 35% 정도 되는 어려운 문제였다. 꽤나 까다롭고 예상치 못한 부분이 있어서 2일 정도 계속 고민했던 것 같다. 이전 정수 삼각형 문제와 같이 마지막 계단으로 가는데 누적합이 최대가 되는 경로를 찾아 그 최대 누적합을 출력하는 문제이다. 동적 계획법 문제들이 그렇듯 메모이제이션과 점화식을 잘 찾아내면 해결할 수 있지만 이번 포스팅에선 내가 실패했던 케이스와 이를 해결한 과정을 기록하고자 한다.

 

---

실패한 케이스

문제의 조건은 세 개이다. 계단은 한 칸 혹은 두 칸씩 오를 수 있으며 연속된 세 개의 계단은 밟지 못하고 마지막 계단은 '반드시' 밟아야 한다.

 

문제는 이전 정수 삼각형 문제와 비슷하기 때문에 이 역시도 그와 같은 방법으로 DP 배열에 해당 칸까지의 최댓값을 저장해가며 메모이제이션을 하려고 했고 점화식 또한 마지막 계단을 기점으로 시작점까지 내려가는 Top-Down 방식과 한 번에 한 개 혹은 두 개의 계단을 오를 수 있기 때문에 F(N) = MAX(F(N-1), F(N-2)) + C(N)으로 생각했다. 즉, C는 비용 함수, 여기에선 N 번째 계단에 적힌 점수가 될 것이고 F(N)은 N번째 계단까지의 최대 누적합이 된다.

추가로 연속된 세 개의 계단을 오를 수 없기 때문에 만약 F(N-1)로 바로 직전 계단으로 내려가야 하는 상황이면 count+1을 주어 만약 count==2가 되면 return 0을 해주어 연속된 세 칸 이동에 제약을 주었다. 코드는 다음과 같다.

 

public static int stair(int N,int count){
  if(DP[N]==-1) {
  	if(count==2) {
  		return 0;
  	}else return DP[N] = Math.max(stair(N-1,count+1), stair(N-2,0))+ cost[N];
  }return DP[N];
}

DP배열을 -1로 초기화하였기 때문에 DP [N]이 -1인지 아닌지에 따라 방문 여부를 확인하였다.

방문하지 않은 계단이라면 그때의 count가 2이면 연속된 계단이므로 0을 반환하고 만약 그렇지 않으면 다음 단계를 진행하였다. stair(N-1)로 갈 때면 count+1을 해주고, stair(N-2)로 갈 때면 0으로 count를 초기화하였다. 0을 반환하는 이유는 Math.max(stair(N-1), stair(N-2)) 이기 때문에 0을 리턴하면 다른 경우의 수에 밀리기 때문에 선택되지 않을 것이라 생각했다. 전체 코드는 다음과 같다.

 

public class Main {
	public static int[] DP;
	public static int[] cost;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		DP= new int[N+1];
		cost = new int[N+1];
		StringTokenizer st;
		for (int i=1; i<N+1;i++) {
			st = new StringTokenizer(br.readLine());
			cost[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.fill(DP, -1);
		DP[0] = cost[0];
		DP[1] = cost[1];
		
		System.out.println(stair(N, 0));
	}
	public static int stair(int N,int count){
		if(DP[N]==-1) {
			if(count==2) {
				return 0;
			}else return DP[N] = Math.max(stair(N-1,count+1), stair(N-2,0))+ cost[N];
		}return DP[N];
	}
}

 

0번째 계단 즉, 시작점이 고려되어야 하기 때문에 DP배열과 cost 배열은 N+1 사이즈로 만들고 DP 배열은 -1로 초기화, cost배열은 입력값을 할당하였다. 

 

이렇게 풀면발생하는 문제는 이와 같다. 

 

 

 

 

 

---

 

해결하자

재귀함수를 호출할 때 직전 계단(N-1)을 호출하면 그 계단이 연속된 계단인지 아닌지에 따라 값이 변동한다. 즉, 호출한 그 계단이 연속으로 밟은 세 번째 계단이었는지 아닌지에 따라 최댓값이 다르게 나오기 때문에 메모이제이션이 불가능하다. 이를 해결하기 위해선, 직전 계단을 호출하는 것이 아니라 N-2, N-3 계단을 호출하되 N-3 계단을 호출했을 때는 N-1번째 cost를 더해준 값과 N-2 계단의 비용 중 Max값을 선택해야 한다는 것이다. 코드로 보면 다음과 같다.

 

public static int stair(int N){
	if(DP[N]==-1) {
		DP[N] = Math.max(stair(N-2), stair(N-3)+cost[N-1])+ cost[N];
	}return DP[N];
}

전체 코드 ↓

import java.io.*;
import java.util.*;


public class Main {
	public static int[] DP;
	public static int[] cost;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		DP= new int[N+1];
		cost = new int[N+1];
		StringTokenizer st;
		for (int i=1; i<N+1;i++) {
			st = new StringTokenizer(br.readLine());
			cost[i] = Integer.parseInt(st.nextToken());
		}
		Arrays.fill(DP, -1);
		DP[0] = cost[0];
		DP[1] = cost[1];
		if (N >= 2) {
			DP[2] = cost[1] + cost[2];
		}
		
		System.out.println(stair(N));
	}
	public static int stair(int N){
		if(DP[N]==-1) {
			DP[N] = Math.max(stair(N-2), stair(N-3)+cost[N-1])+ cost[N];
		}return DP[N];
	}
}

N-3 계단을 호출해주기 때문에 DP [2]의 값도 할당을 해야 한다. 그렇지 않으면 N=-1이 되어 ArrayIndexOutOfBoundsException 에러가 뜨기 때문이다.