[백준알고리즘-JAVA]2579번 풀이(계단 오르기) - 초보도 이해하는 풀이

안녕하세요

인포돈 입니다.

백준 알고리즘 2579번 풀이입니다. 

* 참고사항
 - 개발환경은 eclipse을 기준으로 작성되었습니다.
 - java언어를 이용하여 문제를 풀이합니다.
 - 알고리즘 문제는 풀이를 보고 해답을 찾는 것도 중요하지만 무엇보다 스스로 풀이를 시도해봐야 합니다!!
(해당 풀이를 보기 전 충분히 문제에 대해 고민해봐야 합니다!)
 - 해당 풀이 말고도 수많은 풀이 방법이 존재합니다.

---

백준 2579 (계단 오르기)

문제

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

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

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

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음다음 계단으로 오를 수 있다.
연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
마지막 도착 계단은 반드시 밟아야 한다.
따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

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

입력

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

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

출력

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

입력 예시

6
10
20
15
25
10
20

출력 예시

75

성공 코드

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

public class Main {

	static int N ;
	static Integer[] arr;
	static Integer[] dp;
	
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());;
		
		arr = new Integer[N+1];
		dp = new Integer[N+1];
		
		for(int i = 1 ; i <= N ; i++) {
				arr[i]=Integer.parseInt(br.readLine());
		}
		
		dp[0] = 0;
		dp[1] = arr[1];
		
		if(N>1)
		dp[2] = arr[2]+arr[1];
		
		System.out.println(max(N));
		
}
	public static int max(int num) {
		
		if(dp[num]==null) {
			dp[num] = Math.max(max(num-2), max(num-3)+arr[num-1])+arr[num];
		}
		return dp[num];
	}
}

계단 오르기 알고리즘은 처음 접해본다면, 어느 정도 헷갈릴만한 문제라고 생각합니다. 코드는 간단해 보이지만 비교해야 할 대상을 2가지로 나누는 것이 곳 문제의 핵심이었습니다. (직접적으로 말하면 Math.max부분입니다.)

 

해당 문제를 정확히 이해하고 STEP을 따라가 보죠 

---

알고리즘 흐름도

입력받기 -> 초기값 설정해 주기 -> 재귀 구현하기 -> 최댓값 출력하기

---

STEP1 초기값 설정해주기

arr = new Integer[N+1];
		dp = new Integer[N+1];
		
		for(int i = 1 ; i <= N ; i++) {
				arr[i]=Integer.parseInt(br.readLine());
		}
		
		dp[0] = 0;
		dp[1] = arr[1];
		
		if(N>1)
		dp[2] = arr[2]+arr[1];

네 길어 보여도 사실 별거 없습니다. 여기서 N은 사용자에게 제일 처음 받았던 입력값입니다. 입력 예시로는 6이 되겠군요.

 

 6번을 반복하는 반복문을 이용해 나머지 값들도 입력받아 arr배열에 넣어줍니다. 그 후 dp [0]과 dp [1]을 arr [1]로 초기화해줍니다. 여기서 각각 arr과 dp를 N+1로 해주었기 대문에 이런 식으로 초기화해줍니다.

 

왜냐하면 dp배열은 각 계단의 최댓값을 표현하는 배열이기 때문이죠. 어떠한 계단도 없으면 0 첫 번째 계단은 바로 자기 자신이기 때문입니다.

 

아래 if문으로 dp [2]를 해준 이유는 어떠한 값이더라도 계단이 2개 이상이라면 2번째 계단의 최댓값은 첫 번째 계단과 2번째 계단을 더한 값과 같기 때문입니다.

 

자 이제 벌써 헷갈리시는 분들이 있으실 수 있습니다. 이거를 어떻게 생각해내??? 이럴 수도 있습니다. 그러나 문제의 핵심 어떠한 것을 비교할지 생각해보면 보다 간단히 생각해 낼 수 있습니다. 다음 STEP에서 이해해 보죠

---

STEP2 문제 이해하기 + 재귀 구현하기

문제에서 원하는 것은 무조건 마지막 계단을 밟아야 한다는 것입니다. 그리고 조건이 있죠 3번 연속해서 밟을 수 없습니다. 그렇다면 저희는 경우의 수를 나누어 주어야 합니다.

 

입력 예시를 예로 들며 설명해 드리겠습니다.

6계단 이 있고 마지막 6번째 계단을 밟아야 합니다.

 - 6, 4번째 계단을 밟은 경우

 - 5, 5번째 계단을 밟은 경우

이 2가지로 나누어서 생각해야 합니다. 무엇이 최대의 값이 필요한지

	public static int max(int num) {
		
		if(dp[num]==null) {
			dp[num] = Math.max(max(num-2), max(num-3)+arr[num-1])+arr[num];
		}
		return dp[num];
	}

기본적으로 메모이제이션을 통해서 NULL이라면 재귀를 하도록 합니다. 비교해야 하는 값은 4번째 계단을 밟은 경우 5번째 계단을 밟은 경우로 나누어 생각해줍니다.

 

max(num-2)의 경우 4번째 계단을 밟은 경우

max(num-3) + arr [num-1]은 3번째 5번째 계단을 밟은 경우입니다. 둘 중의 큰 최댓값이 바로 저희가 원하는 값이 되는 거죠.

 

(그런데 왜 굳이 3번째 계단을 고려해 줘야 하나요? : 그 경우 만약 3번째 계단을 고려 안 해준다면, 연속해서 3번의 계단을 밟으면 안 된다는 조건이 만족되지 못하기 때문이죠. )

---

사실 이번 알고리즘은 이전에 이와 같은 형식의 문제를 풀어본 후에 푼 문제여서 한 번에 방법이 떠올려지긴 했습니다. 그러나 저도 이러한 문제를 처음 접해본다면, 어떠한 방식으로 접근해야 할지 감을 잡지 못했을 겁니다. 다시 한번 되돌아보면서 드는 생각은 1. 점화식 2. 어떠한 방식으로 조건을 만족할 것인가 이 2가지가 동적 계획법의 핵심이라는 생각이 듭니다.