[Java] baekjoon_2579 : 계단 오르기

다이나믹 프로그래밍

계단 오르기 : Silver3

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

2579번: 계단 오르기

 

 

첫 번째 작성한 코드

import java.io.*;

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
  public static void main(String[] args) throws IOException {
    int stairs = Integer.parseInt(br.readLine());
    int[] score = new int[stairs + 1];

    for (int i = 1; i <= stairs; i++) {
      score[i] = Integer.parseInt(br.readLine());
    }
    br.close();

    int[] g = new int[stairs + 1];
    int[] h = new int[stairs + 1];
    h[1] = score[1];

    for (int i = 2; i <= stairs; i++) {
      g[i] = h[i - 1] + score[i];
      h[i] = Math.max(h[i - 2], g[i - 2]) + score[i];
    }
    bw.write(Math.max(g[stairs], h[stairs]) + "\n");
    bw.close();
  }
}

 

 

ㄴ g 배열은 이전 계단을 밟지 않고 i번째 계단에 도달했을 때의 최대 점수를 저장한다.
ㄴ h 배열은 이전 계단을 밟고 i번째 계단에 도달했을 때의 최대 점수를 저장한다.
ㄴ 각 계단에서의 최대 점수는 이전 계단에서의 최대 점수에 현재 계단의 점수를 더한 값과 그 이전 계단에서의 최대 점수 중 더 큰 값을 선택하여 저장한다.
ㄴ 마지막 계단에서는 이전 계단을 밟고 올라온 경우와 이전 계단을 밟지 않고 올라온 경우 중 더 큰 값이 최종 결과가 된다.

=> 계단의 개수에 해당하는 g 배열과 h 배열의 마지막 값 중 더 큰 값을 선택하여 최종 결과를 출력한다.

 

재귀함수 뽑아내기

dp[4] = max(dp[2], dp[1] + score[3]) + score[4]

 

 

두 번째 작성한 코드

import java.io.*;

public class Main {
  private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
  
  public static void main(String[] args) throws IOException {
    int stairs = Integer.parseInt(br.readLine());
    int[] score = new int[stairs + 1];
    int[] dp = new int[stairs + 1];

    for (int i = 1; i <= stairs; i++) {
      score[i] = Integer.parseInt(br.readLine());
    }
    br.close();

    dp[1] = score[1];
    if (stairs > 1) {
      dp[2] = score[1] + score[2];
    }
    for (int i = 3; i <= stairs; i++) {
      dp[i] = Math.max(dp[i - 2], dp[i - 3] + score[i - 1]) + score[i];
    }
    bw.write(dp[stairs] + "\n");
    bw.close();
  }
}

 

ㄴ 다이나믹 프로그래밍의 Bottom up 방식을 이용했다.

ㄴ 주의할 점은 dp[i] = Math.max(dp[i - 2], dp[i - 3] + score[i - 1]) + score[i]; 이 코드에서, 연속된 블럭의 경우의 수는 재귀호출이 아니라 이미 입력받은 배열의 값을 더해주어야 한다는 점이다.
ㄴ 두 계단 전의 경우와(N-2) 와 직전 계단을 밟고(N-1), 그 이전에는 두 계단 이전의 경우(N-3)에서 연속되지 않는 위치인 N-2와 N-3에 대해서만 재귀호출을 해주어야 한다. 

ㄴ 현재 인덱스 i 에 대해 두 칸 전(i - 2)의 '저장 값'과 한 칸 전(i - 1)의 값 + 세 칸 전(i - 3)의 '저장 값' 중 큰 값을 현재 i 계단의 값과 합하여 DP배열에 저장해주면 된다.

 

 

// 두 번째 계단을 오를 때까지 초기화
dp[1] = score[1];
if (stairs > 1) {
  dp[2] = score[1] + score[2];
}

// 세 번째 계단부터 시작하여 마지막 계단까지 순회하며 얻을 수 있는 최대 점수를 계산
for (int i = 3; i <= stairs; i++) {
  dp[i] = Math.max(dp[i - 2], dp[i - 3] + score[i - 1]) + score[i];
}

 

ㄴ 현재 위치 i에 있는 계단을 오를 때의 최대 점수를 구한다.

ㄴ dp[i - 2]는 현재 위치의 계단을 오르기 위해 직전 계단을 밟았을 경우의 점수 합이다.
ㄴ dp[i - 3] + score[i - 1]는 현재 위치의 계단을 오르기 위해 두 칸 앞의 계단을 밟았을 경우의 점수 합이다.

ㄴ이전에 세 칸 연속으로 계단을 밟으면 안 되므로, 두 칸 앞의 계단을 밟을 때는 직전 계단을 밟지 않은 상태여야 한다.
ㄴ 두 경우 중에서 더 큰 값에 현재 계단의 점수를 더해준 값이 현재 위치의 계단을 오를 때 얻을 수 있는 최대 점수이다.

 

=> 이렇게 각 위치의 계단을 오를 때 얻을 수 있는 최대 점수를 계산하여 dp[stairs]에는 마지막 계단까지 오를 때의 최대 점수가 저장된다.