[백준] 2579번 계단 오르기

1. 문제

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

계단을 오르면서 각 계단에 적힌 점수를 얻을 때, 도착점까지 도달하는 과정에서 얻을 수 있는 최대 점수를 구하는 문제이다.
계단을 밟는 규칙은 다음과 같다.

1. 한 번에 한 계단 또는 두 계단씩 이동할 수 있다.
2. 연속된 세 개의 계단을 모두 밟을 수 없다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

2. 풀이

각 계단 n에 도착하는 방법은 두 가지로 나뉜다.

1️⃣ n-1번째 계단을 밟고 오는 경우

• 연속 세 계단을 밟을 수 없으므로 (n-3)번째 계단에서 n-1번째 계단을 밟고 n번째 계단으로 이동해야 한다.
• 점수는 dp[n-3] + arr[n-1] + arr[n]

2️⃣ n-2번째 계단을 밟고 오는 경우

• n-2번째 계단에서 바로 n번째 계단으로 이동할 수 있다.
• 점수는 dp[n-2] + arr[n]

두 경우 중 최댓값을 선택해야 한다.
따라서 점화식은 다음과 같이 표현할 수 있다.

dp[n] = Math.max(dp[n-3] + arr[n-1], dp[n-2]) + arr[n]

🔑 코드

dp[1] = arr[1];
if (n >= 2)
	dp[2] = arr[1] + arr[2];

첫 번째 계단을 밟는 경우와 두 번째 계단을 밟는 경우에 대해 기본적인 초기값을 설정한다.

for (int i=3; i<=n; i++) 
	dp[i] = Math.max(dp[i-3] + arr[i-1], dp[i-2]) + arr[i];

점화식을 이용하여 n까지 각 계단까지 오르는 최대 점수를 저장한다.

3. 소스 코드

import java.util.*;
import java.io.*;

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[] dp = new int[n+1];
        int[] arr = new int[n+1];
        for (int i=1; i<=n; i++)
            arr[i] = Integer.parseInt(br.readLine());

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