백준 2579. 계단 오르기

문제 링크

난이도	정답률(_%)
Silver 3	37.348%

설계

• 총 계단의 개수 N (<= 300)
• 마지막 계단은 꼭 밟아야하고, 연속 3개의 계단을 밟을 수는 없으므로 계단을 오를 수 있는 경우의 수는 두가지이다. n번째 계단은 n - 3, n - 1, n 또는 n - 2, n번째 계단을 밟고 올라올 수 있다.

시간 복잡도

• O(N)

공간 복잡도

• 각 계단의 점수를 저장한 배열 N (<= 300)
• 계단을 올랐을 때 최대 점수를 저장한 배열 N + 2 (<= 302)

풀이

• 0, 1, 2 번째 계단은 식이 다르므로 미리 최대값을 지정해준다.
  • 0: 0번째
  • 1: 0 + 1 번째
  • 2: 0 + 2 또는 1 + 2번째

여기서 계단이 1, 2개일 때는 ArrayIndexOutOfBoundsException이 발생해서, if문을 쓸까 하다가 괜히 코드가 쓸데없이 길어지는 것 같아 삼항 연산자를 사용했다.

삼항 연산자를 사용하기 위해서는 할당되는 값인 score는 그 크기만큼 생성돼야했기 때문에 최대 점수를 저장한 배열은 N + 2 개가 생성되도록 했고, 점수의 계산은 길이가 충분할 때만 하도록 했다.

• 3번째 계단부터는 n - 3, n - 1, n번째 계단을 밟거나 n - 2, n번째 계단을 밟는 점수 중 큰 점수를 저장하면서 올라간다.

결과

메모리	실행 시간
13144KB	72ms

코드

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

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

        int stairNumber = Integer.parseInt(br.readLine());
        int[] stairs = new int[stairNumber];

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

        int[] score = new int[stairNumber + 2];

        score[0] = stairs[0];
        score[1] = stairNumber > 1 ? stairs[0] + stairs[1] : 0;
        score[2] = stairNumber > 2 ? Math.max(stairs[0] + stairs[2], stairs[1] + stairs[2]) : 0;

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

        bw.write(String.valueOf(score[stairNumber - 1]));

        bw.flush();
        bw.close();
    }
}