[JAVA] BOJ 백준 2579번 - 계단 오르기

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

2579번: 계단 오르기

---

2. 내가 푼 방법

처음엔 재귀만 이용했는데 시간초과를 해결하지 못하여 정답을 본 문제이다.

먼저 점화식를 찾아야 했다. 처음 코드가 재귀로 작성됐기 때문에 빠르게 찾을 줄 알았는데 실패했다.

 

인덱스 값에 접근하기 편하게 배열 길이를 N+1로 설정한 것을 참고바라면서 아래 그림을 봐보자.

N번째에 도착하기 위해 올 수 있는 방법은 두가지가 있다.

- N-2에서 이동해 N에 도착

- N-1에서 이동해 N에 도착, 하지만 N-3에서 와야 한다는 필수조건이 필요

 

따라서 해당 인덱스까지 올 수 있는 가장 큰 값을 저장해두는 count라는 배열을 사용한 점화식은 아래와 같다.

 ** step 배열은 저장된 계단 값이다.

count[idx] = Math.max(count[idx-2], count[idx-3]+step[idx-1]) + step[idx];

 

하지만 우리가 모르는 값은 count[idx] 값을 모르기 때문에 재귀를 통해서 이를 리턴을 해주어야한다.

public static int dp (int idx) {

    if (count[idx] == -1) {  // Main에서 count 배열에 대한 초기화를 -1로 해둠.
        count[idx] = Math.max(dp(idx-2), dp(idx-3)+step[idx-1]) + step[idx];
    }

    return count[idx];
}

 

재귀를 구현할 때 필요한 것은 무엇인가?

바로 Base Condition이다. 언제까지 재귀를 돌릴 것인가에 대한 고민이 남았는데

1) count 배열의 초기값을 -1로 채우기

2) count[0], count[1], count[2]에 대한 초기값을 설정

 

이로써 문제는 풀릴 것이다.

---

3. 자바 코드

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

class Main {
    static int N;
    static int[] step;
    static int[] count;

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

        N = Integer.parseInt(br.readLine());
        step = new int[N+1];
        step[0] = 0;

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

        count = new int[N+1];
        Arrays.fill(count, -1);
        count[0] = step[0];
        count[1] = step[1];

        if (N >= 2) {
            count[2] = step[1]+step[2];
        }

        bw.write(dp(N)+"");

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

    public static int dp (int idx) {

        if (count[idx] == -1) {
            count[idx] = Math.max(dp(idx-2), dp(idx-3)+step[idx-1]) + step[idx];
        }

        return count[idx];
    }
}

---

4. 결과 및 회고

아 어렵다! 점화식 찾는 게 제일 싫어....