0%

[백준/2579] 계단 오르기

작성일 Edited on In Disqus:

Baekjoon Online Judge - 2579

Review

  • 포도주 시식이랑 비슷한 문제.

  • 포도주 시식이랑 다른 점은 무조건 마지막 칸을 밟아야 한다는 것이다.

  • 경우는 총 두 가지 - 마지막 칸을 밟았을 때

    1. 이전 계단을 밟지 않은 경우
    2. 이전 계단을 밟을 경우

  • 각각의 경우를 점화식으로 나타내면 다음과 같다.

    1. dp[i] = dp[i-2] + stair[i]
    2. dp[i] = dp[i-3] + stair[i] + stair[i-2]

  • 여기서 dp[]는 점수의 최대값이 되고, stair[]는 계단의 점수다.

Code (JAVA)

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
29
30
31
import java.util.*;

public class Main {
  
  public static void main(String args[]) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    
    int[] stair = new int[N + 1];
    int[] dp = new int[N + 1];
    
    for(int i = 1; i <= N; i++) {
      stair[i] = sc.nextInt();
    }
    
    // 초기화
    dp[0] = 0;
    dp[1] = stair[1];
    dp[2] = dp[1] + stair[2];
    
    // 최대값 찾기
    for(int i = 3; i <= N; i++) {
      dp[i] = Math.max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i]);
    }
    
    System.out.println(dp[N]);
    sc.close();
    
  }
  
}