[백준] 2579 _ 계단 오르기 (Java)

nyez·2024년 5월 21일

DP 백준

Coding Test

목록 보기

4/11

정답코드와 결론은 맨 아래에-!!

Dynamic - Procraming(DP)문제로 푸는 방법(공식)만 알면 풀어낼 수 있다.

문제 이해

이 문제에서 사용되는 변수는 아래와 같다.
int n : 계단의 수
int[] stair : 각 계단이 가지고 있는 값
int[] dp : 조건에 따라 누적되는 계단의 값

문제에는 아래와 같은 조건이 있다.

[ 조건 ]

현재 위치로부터 +1 ~ +2까지만 이동 가능
한번에 +3 이상 이동 불가
이동할 수 있는 최댓값

위의 조건을 충족한다는 전제 하에 0, 1, 2번째 자리에는 고정 값이 입력되어야 한다.

[ 고정 값 ]

dp[0] = stair[0]
: 0번째 계단의 값이 dp에 그대로 입력됨
dp[1] = Math.max(stair[0] + stair[1], stair[1])
: 계단 0번째, 1번째 값을 더한 것과 only 두 번째 값 중 더 큰 것을 dp[1]에 넣음
dp[2] = Math.max(stair[0] + stair[2], stair[1] + stair[2])
: 계단 0 + 계단 2와 계단 1 + 계단 2의 값 중 더 큰 값을 dp[2]에 넣음

위의 고정값은 계단의 최댓값을 구하는 방식과 비교하면 알 수 있다.

[ 경우의 수 ]

현재 위치가 계단 3 일 때, 연속으로 3개의 계단을 오르지 않고 구할 수 있는 최댓값의 방식은

[ 0번 + 1번 + 3번 ] 이거나
[ 1번 + 2번 + 3번 ] 이다.

이는 현재 위치가 i일 때 dp[i] = Math.max(dp[i-2] + stair[i], dp[i-3] + stair[i-1] + stair[i]) 로 나타낼 수 있다.

코드 이해

먼저 int형 배열 stair에 계단의 값을 입력받은 후 dp에 값을 저장하는 방식으로 작성했다.

stair 값 입력받기
dp 배열 고정 값 입력하기 (0,1,2번 인덱스 값)
dp 3부터의 공식 입력으로 값 구하기

주의할 점 : dp의 0, 1, 2번째에는 고정값을 부여한다.
이 말인 즉슨, 어떤 수(ex. 1)가 들어와도 3개의 배열은 보장되어야 한다는 의미이다.

>> dp 배열 선언 시 n+3을 입력하여 3개의 공간은 보장되도록 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class App {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    int[] stair = new int[n + 3];
    int[] dp = new int[n + 3];

    for (int i = 0; i < n; i++) {
      stair[i] = Integer.parseInt(br.readLine());
    }

    // 아래에서 i-3하려면 최소 3개 만들어져있어야 함
    dp[0] = stair[0];
    dp[1] = Math.max(stair[0] + stair[1], stair[1]);
    dp[2] = Math.max(stair[0] + stair[2], stair[1] + stair[2]);

    for (int i = 3; i < n; i++) {
      dp[i] =
        Math.max(dp[i - 3] + stair[i - 1] + stair[i], dp[i - 2] + stair[i]);
      // stair : 10 20 15 25 10 20
      // dp : 10 max(10, 20) max(25, 20) max(25, 35) max(30+25, 10+15+25)
    }

    System.out.println(dp[n - 1]);
  }
}