[BOJ/Java] 2579. 계단 오르기

[BOJ/Java] 2579. 계단 오르기

2579번: 계단 오르기

---

문제 해석

이 문제는 주어진 계단을 오르는 최적의 방법을 찾는 다이나믹 프로그래밍 문제이다. 계단에는 점수가 부여되어 있으며, 한 번에 1개 혹은 2개의 계단을 오를 수 있다. 단, 연속된 세 개의 계단을 모두 밟으면 안 된다. 최종 목적은 계단 꼭대기에 도달할 때 최대 점수를 얻는 것이다.

풀이 과정

제출된 코드는 다이나믹 프로그래밍 방식을 사용하여 각 계단에 도달했을 때의 최대 점수를 계산한다. 코드는 다음과 같은 접근 방식을 사용한다:

1. 입력 처리: 사용자로부터 계단의 개수(N)와 각 계단의 점수를 입력 받는다.
2. 초기 조건 처리: 만약 계단이 하나 또는 두 개인 경우, 간단한 덧셈으로 결과를 얻는다.
3. 다이나믹 프로그래밍 계산: 세 개 이상의 계단이 있는 경우, 각 계단에 대해 두 가지 경우의 최대 점수를 계산한다. 한 계단을 건너 뛰어 오르는 경우와 두 계단을 건너뛰어 오르는 경우를 비교하여 더 높은 점수를 선택한다.

코드

package edu.ssafy.im.BOJ.Silver.S3.No2579;

import java.io.*;

public class Main {
    private static int N;
    private static int[] stairs, dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());

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

        if (N == 1) sb.append(stairs[1]);
        else if (N == 2) sb.append(stairs[1] + stairs[2]);
        else sb.append(sol());

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    private static int sol() {
        dp = new int[N + 1];

        dp[1] = stairs[1];
        dp[2] = stairs[1] + stairs[2];

        for (int i = 3; i < N + 1; i++) {
            dp[i] = Math.max(dp[i - 2] + stairs[i], dp[i - 3] + stairs[i - 1] + stairs[i]);
        }

        return dp[N];
    }
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 O(N)이다. 계단의 개수에 따라 각 계단에서 최대 점수를 계산하는 데 상수 시간이 소요되며, 모든 계단을 한 번씩만 처리하면 된다.