Backjoon(백준) 2579번 - 계단 오르기(Java)

어느정도 풀다가 막혀서 이 해설을 보시는 분은, 풀이 힌트를 한번 보고 다시 혼자서 풀어보세요

 

1. 풀이 힌트

 - 꼭대기의 마지막 계단 부터 가정하여, 어떤 방식으로 플레이어가 꼭대기에 도착해야 최대 스코어를 받을 수 있을 지 고민하기.

2. 풀이 과정 

 - 계단이 2개 이하일 때 최댓값은 각 계단을 더한 값이 된다.

 - 계단이 3개 이상일 때 부터는 꼭대기(i)에 최대값을 유지하면서 올라갈 수 있는 방법은 2가지가 된다.

 1) 꼭대기(i)의 직전 계단(i - 1)을 밟은 경우

  - 플레이어가 꼭대기의 직전 계단을 밟고 올라온 경우 꼭대기까지 왔을 떄 플레이어의 최대 값은

  - "꼭대기(i) + 꼭대기 직전(i - 1) + 꼭대기 직전 -2 계단(i - 3)까지의 최댓값"이 된다.

  - 한번에 연속된 3개의 계단을 동시에 올라갈 수 없기 때문에 마지막에 꼭대기 직전 -2 계단까지의 최댓값을 더해준다.

 

 2) 꼭대기(i)의 전전 계단(i - 2)에서 점프해서 올라온 경우

  - "꼭대기(i) + 꼭대기 전전 계단(i - 2)까지의 최댓값"

  - 한 계단 또는 두 계단을 건널 수 있기 때문에 꼭대기 전전 계단까지의 최댓값도 2가지의 경우로 나뉘어서 판별하기 떄문에 꼭대기 전전계단까지의 최댓값을 구하고 꼭대기의 값과 더해준다

3. 핵심 포인트

 - 다른 DP문제와 동일하게, 경우에 수에 따라 점화식을 도출할 수 있고, 주어진 조건을 구하기 위해 누적합을 저장하는 배열을 선언해야한다.

4. 코드 구현

import java.util.Scanner;

public class Upstairs {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int jump = 0, noJump = 0;
        int n = sc.nextInt();
        int[] stairs = new int[301];
        int[] dp = new int[301];
        
        for (int i = 1; i <= n; i++) {
            stairs[i] = sc.nextInt();
        }
        
        dp[1] = stairs[1];
        dp[2] = stairs[1] + stairs[2];
        
        for (int i = 3; i <= n; i++) {
            noJump = stairs[i] + stairs[i - 1] + dp[i - 3];
            jump = stairs[i] + dp[i - 2];
            
            dp[i] = Math.max(noJump, jump);
        }
        
        System.out.println(dp[n]);

    }

}

 

문제 링크 ( https://www.acmicpc.net/problem/2579 )