[JAVA] BOJ(백준) - 계단 오르기 - 2579

문제 내용

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

2579번: 계단 오르기

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

<그림 1>

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

<그림 2>

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

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

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

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

입력

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

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

출력

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

 

---

문제 접근 방법

최근 풀었던 DP문제 중 처음 접근할때 가장 어려웠던 문제이다.

어려웠던 이유는 문제에서 주어진 조건 때문인데

 

연속된 세계단 밟는거 x,

마지막 계단 무조건 밟아야됨,

계단은 한칸 or 두칸씩 이동 가능.

 

이라는 조건에 맞게 코드를 무작정 작성하려다 보니 어려웠던 것 같다.

처음엔 계단 한개를 밟고 올라갈때, 두개를 밟고 올라갈때의 두가지 경우로 나누고 두가지 경우 중 최댓값을 dp배열에 저장하면서 cnt 변수를 활용해 연속으로 한계단씩 밟았을땐 두계단을 밟고 올라가는 방향으로 코드를 작성했다.

 

이렇게 코드를 작성 했을때의 내생각에 문제점은

 

첫번째로 마지막 계단을 밟을수도 안밟을수도 있다는점.

두번째로 계단을 밟는 순서와 값에 따라 반례가 존재 할수도 있다는 점. ex) 1 2 3 4 5 7 6

두가지 문제점이 존재한다.

 

이를 해결하기 위해

첫번째로 마지마 계단을 무조건 밟을수 있게 코드를 작성.

두번째로 정확한 점화식으로 코드를 작성.

하는 것이다.

 

특히 두번째의 경우 기존엔 기본적으로

dp[i+1] = Math.max(dp[i+1], dp[i]+stair[i+1])

dp[i+2] = Math.max(dp[i+2], dp[i]+stair[i+2])

를 활용했으나.

마지막 계단을 밟을때 바로 전계단에서 올라온 경우와 2계단 전에서 점프 뛰어 올라온 경우로 나눠서

"dp[i] = Math.max(점프뛰고 올라온 경우, 바로전 계단에서 올라온 경우) + 현재계단 값" 즉,

dp[i] = Math.max(dp[i-2], dp[i-3]+stair[i-1]) + stair[i]

로 처리했다.

참고로 직전 계단에서 올라온 경우의 값은 무조건 그전에 점프뛴 경우 하나다.

 

위의 식을 활용하면 재귀와 for문으로 풀수 있다.

 

---

풀이

for문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_2579_1 {
	static int[] stair;
	static int[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		//0번 인덱스는 시작점
		stair = new int[n+1];
		dp = new int[n+1];
		
		for(int i=1; i<=n; i++) {
			stair[i] = Integer.parseInt(br.readLine());
		}
		
		dp[1] = stair[1];//1번 값 초기화
		
		//dp[2]의 값을 초기화 해줘야하는데
		//n이 1이 될 경우엔 dp[2]는 없으니까 n>=2 일 때만 dp[2]를 초기화해줌.
		if(n>=2) {
			dp[2] = stair[1]+stair[2];
		}
		
		//3번째 계단 부터 시작하고 마지막 계단 까지 한계단 밟고 왔을때 두계단 점프뛰고 왔을때
		//경우로 나눠서 최댓값을 현재 계단에 누적시켜줌.
		for(int i=3; i<=n; i++) {
			dp[i] = Math.max(dp[i-2], dp[i-3]+stair[i-1])+stair[i];
			
		}
		System.out.println(dp[n]);
	}
}

 

 

재귀

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_2579_2 {
	static int[] stair;
	static int[] dp;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		stair = new int[n+1];
		dp = new int[n+1];
		
		for(int i=1; i<=n; i++) {
			stair[i] = Integer.parseInt(br.readLine());
			dp[i]=-1;//dp배열 -1로 초기화
		}

		dp[1] = stair[1];
		if(n>=2) {
			dp[2] = stair[1]+stair[2];
		}
		
		int max = maxStair(n);
		System.out.println(max);
	}
	
	public static int maxStair(int n) {
		if(dp[n]==-1) {
			dp[n] = Math.max(maxStair(n-2), maxStair(n-3)+stair[n-1])+stair[n];
		}
		return dp[n];
	}
}

 

 

---

마치며

이번 문제는 처음에 점화식을 잘못 생각해서 오래 걸린 문제같다.

항상 DP관련 문제라 생각되면 어떤 점화식이 있을지 찾아보는 습관을 기르자.

그리고 재귀의 경우 풀이에 주석을 많이 달아놓지 않았는데 for문 방식을 이해한다면 재귀도 이해될꺼라 생각된다.