백준 BOJ 2579번 - 계단 오르기

---

접근 방법

 

먼저 이 문제는 DP를 사용하는 문제다.

 

이 문제를 푸는데에 핵심은 1번, 2번 규칙이다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

 

역으로 생각하면 쉽다. n번째의 계단을 밟으려면 경우의 수는 2가지가 있다.

출처 : https://girawhale.tistory.com/3

• n-3을 밟고 n-1을 밟고 오는 경우
• n-2을 밟고 오는 경우

2번 규칙 때문에 이렇게 두 가지 경우밖에 없다.

따라서, n번째 계단의 값은 2가지 경우 중 큰 값 + n번의 값이 해당 계단의 dp값이 된다. 이를 코드로 구현해보자.

---

코드

import java.util.*;
 
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int N = in.nextInt();
		int[] dp = new int[N + 1];
		int[] stairs = new int[N + 1];
 
		for (int i = 1; i <= N; i++) {
			stairs[i] = in.nextInt();
		}
		dp[1] = stairs[1];
      if(N > 1)
         dp[2] = stairs[1] + stairs[2];
		for (int i = 3; i <= N; i++) {
			dp[i] = Math.max(dp[i - 2] , dp[i - 3] + stairs[i - 1]) + stairs[i];
		}
		System.out.println(dp[N]);
	}
}