[JAVA/백준] 동적 계획법 1: 계단 오르기

👀 문제

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

👊 도전

1. 설계

1. 계단이 1부터 n까지 차례대로 계산 방법을 찾아 점화식을 구한다.

2. 구현 (성공 코드)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.Scanner;

/**
 * 
 * @author HEESOO
 *
 */
public class Main {
	public static void main(String[] args){
		Scanner input=new Scanner(System.in);
		int n=input.nextInt();
		int[] array=new int[n+1];
		int[] dp=new int[n+1];
		for(int i=1;i<=n;i++){
			array[i]=input.nextInt();
		}
		
		dp[1]=array[1];
		if(n>1) dp[2]=array[1]+array[2];
		
		for(int i=3;i<=n;i++){
			dp[i]=array[i]+Math.max(array[i-1]+dp[i-3], dp[i-2]);
		}
		
		System.out.println(dp[n]);
	}
}
 

3. 결과

🤟 성공 🤟

4. 설명

1. DP를 이용한다.
   • dp[i]가 i번째 계단에 오르는 최댓값이고, array[i]는 i번째의 점수라고 할 때, 1부터 차례대로 구해본다.
   • i<=2
     dp[1]=array[1]
     dp[2]=array[2]
     1과 2는 이전 값을 더하는 것이 아니기 때문에 규칙이 없으므로 dp에 바로 넣는다.
   • i>2
     i번째 계단에 오르려면 이전 i-1을 밟거나 i-2를 밟아야한다. 이때 i-1을 밟으려면 연속해서 i-2를 밟는 것은 불가능하므로 i-3을 밟아야한다. 이를 식으로 나타내면,
     d[i]=array[i]+Math.max(array[i-1]+dp[i-3], dp[i-2]).
     array[i-1]+dp[i-3]의 의미는, i를 밟기 위해 바로 전의 i-1를 밟아야하므로 해당 i-1의 값이 필요하고, 연속으로 세 번 밟을 수 없기 때문에 i-3도 밟아야 하는데, 1부터 i-3까지의 누적된 dp에 최댓값이 저장되어 있을 것이므로 해당 i-3은 dp배열 값을 가져온다.
     반대로 dp[i-2]의 의미는, 연속해서 세 번 밟은 것이 아니므로 제약 조건이 없기 때문에 1부터 i-2까지의 최댓값이 저장된 dp를 가져와서 여기에 array[i]를 더하면 된다.

👏 해결 완료!

참고

• [DP] 백준 2579 계단오르기(Climbing Stairs) https://limkydev.tistory.com/121