[백준 with JAVA] 2579번 : 계단오르기 - DP

 

2579번: 계단 오르기

2579번: 계단 오르기

 

 

 

문제 보기

 

 

DP 문제이기에 이 문제를 어떻게 세부 문제로 나눠서 점화식을 세울까 고민했습니다.

개인적으로 점화식을 세워서 문제를 맞추는데 성공했지만 다른 분들과 코드를 비교했을 때 내용이 달라

제 코드와 다른 분들의 코드를 비교해서 포스팅 하겠습니다.

 

 

 

---

1. 내 문제 접근법

 

 

문제를 보면 다음과 같은 조건들이 있습니다.

연속해서 세 칸을 올라가지 못한다.

 

저는 이 조건을 보고 계단에서 일정한 규칙으로 움직여야 함을 알 수 있었습니다.

 

한 칸 올라감을 1로

두 칸으로 올라감을 2로 표현하겠습니다.

 

 

 

 

1-1. 문제 규칙 찾기

 

 

• 첫 번째 계단에서 시작할 때

먼저 1로 시작합니다.

그러면 다음과 같은 경우들이 나올 수 있습니다.

1 → 1 → 2

1 → 2 → 1 → 2

1 → 2 → 2

…

 

 

첫번째 칸에서는 1이 오면 다음에 1이 올 수 있습니다.

하지만 다른 계단에서 1이 오면 다음에 2가 올 수 밖에 없습니다.

다른 계단에서 1이 온 경우는 이미 그 전 계단을 밟았기 때문에 연속해서 계단을 2칸을 밟았음을 알 수 있습니다.

 

하지만 예외 계단은 바로 첫 번째 칸입니다.

 

때문에 저는 예외인 첫 번째 칸을 따로 계산해야 한다고 생각했습니다.

그 경우는 바로 1 → 1 → 2 로 시작하는 경우 였습니다.

 

 

 

 

• 두 번째 계단에서 시작할 때

먼저 2로 시작합니다.

2가 나왔을 경우에는 다음과 같은 경우들이 나올 수 있습니다.

2 → 1 → 2 → …

2 → 2 → …

 

처음에 두 칸을 올라가서 시작했을 때는 다음에 1이 나오느냐 2가 나오느냐로 분리가 됩니다.

이 때 1이 나오면 다음에 무조건 2가 나와야합니다.

이 때 2가 나오면 다음에 1 또는 2가 나올 수 있습니다.

 

첫 번째 계단에서 시작할 때랑 같은 조건이 있습니다.

2가 나왔을 때는 그 다음에 1 또는 2가 올 수 있지만

1이 나왔을 때는 무조건 2가 나와야합니다. (첫 번째 계단 시작은 예외 있었죠? 1 → 1 → 2)

 

 

 

정리하자면

저는 다음과 같은 규칙 그리고 예외 상황을 알 수 있었습니다.

1 다음은 무조건 2가 온다.

2 다음은 1, 2 둘 다 올 수 있다.

하지만 첫 번째 계단에서 시작할 때는 다음에 1과 2 둘 다 올 수 있다. (1 → 1 → 2)

 

 

 

 

1-2. 한 칸(1)과 두 칸(2)은 따로 계산해야 한다.

첫 번째 계단에서 시작 했을 경우는 예외로 처리하고 따로 계산하겠습니다.

 

 

 

1-2-1. 따로 계산해야 하는 이유

N 번 계단에 도착했다고 하겠습니다.

N 번 계단에 도착할 수 있는 방법은 두 가지 방법이 있습니다.

N - 1번 계단에서 한 칸(1) 올라오기

N - 2번 계단에서 두 칸(2) 올라오기

 

만약 한 칸(1) 올라온 것이면 다음에 두 칸(2)을 올라가야 합니다.

(N - 1) → (N) → (N + 1) 이 되면 연속된 세 칸이 되기 때문에 안됩니다.

때문에 (N - 1) → (N) → (N + 2) 이렇게 될 수 밖에 없습니다.

 

하지만 두 칸(2) 올라온 것이면 다음에 한 칸(1), 두 칸(2) 둘 다 됩니다.

(N - 2) → (N) → (N + 1)

(N - 2) → (N) → (N + 2)

무엇이 되었든 세 칸 연속해서 올라가는 경우가 아니기 때문입니다.

 

 

 

1-2-2. 한 칸(1) 두 칸(2) 판별하기

저는 다음과 같이 2차원 배열을 선언했습니다.

int[][] dp = new int[3][N + 1]

dp[1][]은 한 칸 올라왔을 때의 계단 합을 의미하고

dp[2][]는 한칸 올라왔을 때의 계단 합을 의미합니다.

 

 

 

 

1-3. 올라갈 수 있는 모든 경우 계산하기

이제 계산을 다음과 같이 할 수 있습니다.

• 이전에 한 칸(1)으로 올라왔을 경우는 다음에 2가 와야 합니다.

 

즉, 다음에 두 칸(2)을 올라가야 할 때의 계단 합을 구하면 됩니다.

• 이전에 두 칸(2)으로 올라왔을 경우는 다음에 1 또는 2가 와야 합니다.

 

즉, 다음에 한 칸(1) 또는 두 칸(2)을 올라갈 때의 계단 합을 구하면 됩니다.

즉, 두 번째 계단에서 부터는 다음과 같은 경우만 올 수 있습니다.

1 → 2

2 → 1

2 → 2

 

 

이 때 (1 → 1 → 2)는 예외로 처리했습니다.

계단을 올라가는 범위는 if문으로 걸어서 해당 범위 일 때만 계단을 올라갔습니다.

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

 

 

 

1-4. 내 최종 코드

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

public class Main {

    static int N;
    static int[] stairs;
    static int[][] dp;

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

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

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

        dp = new int[3][300 + 1];

        dp[1][1] = stairs[1];
        dp[1][2] = dp[1][1] + stairs[2];
        dp[2][2] = stairs[2];
        for (int i = 1; i < N; i++) {
            // 1 -> 2
            if (i + 2 <= N) dp[2][i + 2] = Math.max(dp[2][i + 2], dp[1][i] + stairs[i + 2]);
            // 2 -> 1
            if (i + 1 <= N) dp[1][i + 1] = Math.max(dp[1][i + 1], dp[2][i] + stairs[i + 1]);
            // 2 -> 2
            if (i + 2 <= N) dp[2][i + 2] = Math.max(dp[2][i + 2], dp[2][i] + stairs[i + 2]);
        }
        System.out.println(Math.max(dp[1][N], dp[2][N]));
    }
}

 

 

 

 

 

---

2. 다른 유저분의 코드

제가 출발을 어떻게 해야 해당 목적지에 도착할까 고민해서 풀었다면

다른 분은 도착했을 때 여기서 올 수 있는 가지 수를 생각한거 같습니다.

 

찾게 되는 거는 비슷하나 관점이 달라서 문제 풀이 방식도 다른 것 같습니다.

 

BFS로 풀이 하신 코드를 보니 다음과 같았습니다.

int[] dp = new int[300 + 1];

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

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

제가 만든 점화식의 1/3 이네요 ㅋㅋㅋ

해석하면

i번째 계단을 올라오는데에는 두 가지 방법이 있습니다.

• i - 2번 째 계단 → i번 째 계단 : (두 칸(2))
• i - 3번 째 계단 → i - 1번째 계단 → i번 째 계단 : (두 칸(2), 한 칸(1))

 

내용을 좀 더 자세히 보면 제가 생각했던 것과 같습니다. (당연히 나와야 하는거..?)

i 번 째 계단 전에 i - 1 번째 계단을 밟았느냐 마느냐로 나뉠 수 있습니다.

 

계단을 3칸씩 나뉘어서 보겠습니다.

 

만약 i - 1번째 계단을 밟았으면 그 이전 계단은 i - 2가 아닌 i - 3이어야만 합니다.

즉, dp[i] = dp[i - 3] + stairs[i - 1] + stairs[i] 이 됩니다.

 

그렇지않고 i - 2번 째 계단을 밟고 온 것이라면 그 계단까지의 최대합과 도착 계단을 더하면 됩니다.

dp[i] = dp[i - 2] + staris[i]

 

또 제 코드와 차이점을 알 수 있는게 저는 출발을 어떻게 하느냐에 따라서 갈리기 때문에

한 칸 올라가서 도착했을 때와

두 칸 올라가서 도착했을 때를 따로 계산해줘야 했습니다.

 

하지만 다른 분의 코드는 도착지를 중심으로 봤기에 이미 그 식안에서 해결이 되어 있습니다.

때문에 다른 분의 코드가 훨씬 접근하기 쉽고 좋습니다.