[백준] 2579 계단 오르기 (JAVA) 풀이 - DP

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

재귀 함수를 사용해 풀수도 있지만, 동적 계획법(DP)를 사용해 풀었습니다.

---

풀이방법

1. 점화식의 형태와 의미는 DP[N] = N개의 계단에서 최대 점수로 도출하였습니다.

최대값을 찾는 문제이기 때문에 핵심 점화식에서는 Math.max 함수가 있다는 것을 알 수 있습니다.

 

이를 토대로 계단이 1개 ~ 5개일 경우, 하드 코딩으로 작성해봅니다.

DP[1] = step[1]

DP[2] = step[1] + step[2]

DP[3] = step[1] + step[3]

          = step[2] + step[3] 이므로 max(step[1]+step[3] , step[2] + step[3]) 이다.

DP[4] = step[1] + step[2] + step[4] = DP[2] + step[4]

          = step[1] + step[3] + step[4] = DP[1] + step[3] + step[4] 이므로 max( DP[2] + step[4] , DP[1] + step[3] + step[4] )

DP[5] = step[1] + step[2] + step[4] + step[5] = DP[2] + step[4] + step[5]

          = step[1] + step[3] + step[5] = DP[3] + step[5] 이므로 max( DP[2] + step[4] + step[5], DP[3] + step[5])

 

1번째 계단부터 3번째 계단까지는 하드 코딩으로 작성합니다. 4번째 계단부터는 동일한 패턴이 반복되어지는 것을 볼 수 있습니다. 핵심 점화식은 DP[i] = max(DP[i-3] + step[i-1] + step[i] , DP[i-2] + step[i]) 입니다.

 

이 점화식에 의하면 해당 계단의 최대 점수는, 이전 계단에서 바로 올라온 값과, 이전의 이전 계단에서 올라온 값을 비교하여 산출됩니다. 이 문제의 핵심은 기술된 규칙에 맞는 각 계단들의 최대값을 작은 것부터 저장해가면서 최종 최대값을 구해내야 합니다.

 

2. num이 1인 경우에는 불필요한 로직을 사용하지 않도록 출력한 후 바로 return 합니다.

정답 코드

import java.io.*;
public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());
		int[] step = new int[num+1];
		
       	 	for(int i=1 ; i<=num ; i++) {
			step[i] = Integer.parseInt(br.readLine());
		}
        
        	// 2
		if(num==1) {
			System.out.print(step[1]);
			return;
		}
		
        	// 1
		int[] DP = new int[num+1];
		DP[1] = step[1];
		if(num>=2) DP[2] = DP[1] + step[2];
		if(num>=3) DP[3] = Math.max(step[1]+step[3], step[2]+step[3]);
		for(int i=4 ; i<=num ; i++) {
			DP[i] = Math.max(DP[i-3]+step[i-1]+step[i], DP[i-2]+step[i]);
		}
		
		System.out.print(DP[num]);
	}
}

 

 

느낀점

점화식을 세우는데에 아직 어렵다. DP 문제를 계속 풀어보면서 점화식을 만들고, 코드로 구현하는 연습이 계속 필요할 거 같다.