백준 2579. 계단 오르기

문제 바로가기

계단 오르기

문제 요약

계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는데 계단을 밟으면 계단에 적혀있는 숫자를 점수로 얻게 된다. 계단을 오르는데의 필요한 규칙으로는

1. 계단은 한번에 한 계단 또는 두 계단을 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아선 안된다. (시작점은 제외)
3. 마지막 도착 계단은 무조건 밟아야 한다.

이때, 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

문제 풀이 포인트

처음 적용한 방식은 DFS로 모두 가보는 방식으로 해결하려 했다. 굉장히 간단하게 보이는 문제였고 해결 방식 또한 간단했다. 하지만 계단의 개수가 300개 이하의 자연수인데 비해 시간 제한이 1초로 시간 초과가 발생한다. 그래서 이문제는 동적 계획법(DP, dynamic programming)으로 해결하는 문제이다.

이 문제는

1. i 번째 위치의 계단을 밟지 않는 경우
2. i 번째 위치의 계단을 처음으로 밟는 경우
3. i 번째 위치의 계단을 연속으로 밟는 경우 세 가지로 구분할 수 있다.

   ---

1. i 번째 위치의 계단을 밟지 않는 경우

해당 위치의 계단을 밟지 않으므로 이전에 밟았던 계단의 최대 점수가 현재 위치의 점수가 될 것이다.

2. i 번째 위치의 계단을 처음으로 밟는 경우

해당 위치의 계단을 처음 밟으므로 (i-1 위치를 밟지 않았던 점수) + (현재 위치의 점수)가 현재 위치의 점수가 될 것이다.

3. i 번째 위치의 계단을 연속으로 밟는 경우

해당 위치의 계단을 연속으로 밟았으므로 (i-1 위치의 계단을 처음 밟았을 때의 점수) + (현재 위치의 점수)가 현재 위치의 점수가 될 것이다.

위의 내용을 점화식으로 구분하여 작성하면 해결할 수 있다.

문제 코드[JAVA]

import java.util.*;

public class Main {
  static int N;
  static int[] arr;
  static int[][] dp;
  public static void main(String[] args) throws Exception{
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();
    arr = new int[N+1];
    dp = new int[N+1][3];
    for(int i = 1; i <= N;i++) {
      arr[i] = sc.nextInt();

    }
    for(int i = 1; i <= N; i++) {
      dp[i][0] = Math.max(dp[i-1][1], dp[i-1][2]); // i 번째를 안밟음
      dp[i][1] = dp[i-1][0] + arr[i];             // i 번째를 처음 밟음
      dp[i][2] = dp[i-1][1] + arr[i];             // i-1 번째와 i번째를 연속으로 밟음
    }

    System.out.println(Math.max(dp[N][1], dp[N][2]));
    sc.close();
  }

}