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

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

2579번: 계단 오르기

 

백준 2156 포도주 시식 문제와 비슷한 문제다.

다른 점은 "마지막 도착 계단은 반드시 밟아야 한다."이다.

 

계단 오르기의 경우의 수는 2가지이다.

마지막 도착 계단 밟은 상태에서 n -1 위치의 계단을 밟지 않는 상태 vs n -1 위치의 계단을 밟은 상태

 

위 그림과 같이 2가지 형태로 나올 수 있다.

앞에 n - 2, n - 3 위치의 체크표시가 빨간 이유는 다음과 같다.

n -1 위치의 계단을 밟지 않는 상태일 때 n - 2의 위치의 계단은 꼭 밟아야 한다. 그래야지 최대 값이 나오기 때문이다.

마찬가지로 n -1 위치의 계단을 밟은 상태일 때 n - 3의 위치의 계단은 꼭 밟아야 한다.

 

그러면 점화식이 나오게 된다.

 

최댓값을 저장한 dp 테이블

int[] dp = new int[n + 1];

계단의 점수가 저장된 테이블

int[] values = new int[n + 1];

점화식

if i == 1 dp[i] = values[i]
if i >= 2 dp[2] = values[1] + values[2] (계단이 2개면 선택지는 두 계단을 다 밟는 경우)

dp[i] = Math.max(dp[i - 2], dp[i - 3] + values[i - 1]) + values[i];

 

자바 코드

package main.iyk2h;

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[] values = new int[n + 1];
        int[] dp = new int[n + 1];

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

        dp[1] = values[1];
        if (n > 1) {
            dp[2] = values[1] + values[2];
        }
        for (int i = 3; i <= n; i++) {
            dp[i] = Math.max(dp[i - 2], dp[i - 3] + values[i - 1]) + values[i];
        }
        System.out.println(dp[n]);
    }
}