[백준] 🥈 2579 계단 오르기

📌 난이도

🥈 Silver 3

📌 문제

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

📌 풀이

와… DP문제를 풀면서 느낀점은 아.. 될거같은데? 거의 풀었는데, 아 왜안되지…. 제출: 3%에서 오답 이런 식이였다.
직관적으로 풀려다가 경우의 수를 계산하면서 겉잡을 수 없이 오류가 커지게 된다.

이 문제같은 경우에는 처음에 class step를 만들어서 그 안에 int current와 isSkip, totalStep의 변수를 넣어서 step형식의 리스트를 만들고, 전 주소값의 isSkip이 true이면 -1, -2의 totalStep을 비교하여 더 큰 값에 current를 더하고, isSkip이 false이면 -2주소값에 current값을 더해주었다.
하지만, 도저히 이 방법으로는 이 문제를 해결할 수가 없었다.

이 알고리즘을 개선하면서, 장정 6시간동안이나 고민을 하였는데, 도저히 어떻게 해야할지 하나도 감이 잡히지가 않았다.
그래서 먼저 푼 사람에게 물어보았다.

와… 설명을 듣는데 이해가 전혀 되지 않았다.
앞에서 진짜 열심히 설명을 해주는데, 머리로는 아 저렇게하면 모든 경우의 수를 따르겠지만, 어떻게 저런 생각을 하지…라는 생각밖에 안들었다.
그 방식이란 다음과 같다.

다음과 같이 0의 주소를 밟는 경우의 수는 3가지가 있다.

• -3, -1을 밟는 경우
  • dp[0] = dp[-3] + arr[-1] + arr[0]
• -3, -2를 밟는 경우
  • dp[0] = dp[-3] + arr[-2] + arr[0]
• -2만 밟는 경우
  • dp[0] = dp[-2] + arr[0]

이때 dp의 값은 항상 최대값인데, 2번째 방법과 3번쨰 방법의 수는 사실상 항상 2번째가 더 큰값이 된다.
따라서 1번, 2번값을 Math.max을 이용하여, 더 dp[0]에 저장하면, 모든 dp값은 항상 최대가 된다.

계속 노력하다 보면 언젠가는 이 문제를 보면서 이렇게 쉬운데, 이걸 고생했다고? 하는 날이 오지 않을까... 백준을 풀면서 요즘 항상 부족하다고 느끼게 된다.

📌 Code

package DP;

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

public class N2579 {
    static int[] dp;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int target = Integer.parseInt(st.nextToken());
        arr = new int[target];
        dp = new int[target];
        for (int i = 0; i < target; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = Integer.parseInt(st.nextToken());
        }
        dp[0] = arr[0];
        if (target > 1) {
            dp[1] = arr[1] + arr[0];
        }
        if (target > 2) {
            dp[2] = Math.max(arr[0] + arr[2], arr[1] + arr[2]);
        }
        for (int i = 3; i < target; i++) {
            MakeMax(i);
        }

        System.out.println(dp[target - 1]);
    }

    public static void MakeMax(int index) {
        dp[index] = Math.max(dp[index - 3] + arr[index - 1], dp[index - 2]) + arr[index];
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁