백준 17484 진우의 달 여행 (Small) C++

백준 진우의 달 여행 (Small) 17484 C++ 풀이

---

문제

문제 설명

진우는 우주 여행을 떠나기 위해 N×M 격자로 표현된 공간을 지나야 합니다.
각 칸에는 그 칸을 지나갈 때 필요한 연료 소모량이 적혀 있습니다.
우주선의 이동 규칙은 다음과 같습니다.

• 아래로만 내려갑니다.
• 왼쪽 아래 대각선 (↙)
• 바로 아래 (↓)
• 오른쪽 아래 대각선 (↘)

같은 방향으로 두 번 연속 이동할 수 없습니다.
출발은 첫 번째 행의 어느 칸에서든 할 수 있고, 도착은 마지막 행의 어느 칸이든 가능합니다.
목표는 최소 연료로 마지막 행까지 도달하는 것입니다.

---

테스트케이스

입력
6 4
5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58
출력
29

---

문제 작동 원리

• 3차원 DP(dp[i][j][d])를 사용합니다.
• i = 행
• j = 열
• d = 마지막으로 이동한 방향 (0=↙, 1=↓, 2=↘)
• dp[i][j][d] = (i,j)에 도착했을 때, 마지막 이동이 d였을 때 필요한 최소 연료
• 점화식:

dp[i][j][d] = min(dp[i-1][prev][k]) + arr[i][j] (단, k ≠ d)

• prev는 d에 따라 달라집니다.
• d=0 → prev=j+1
• d=1 → prev=j
• d=2 → prev=j-1
• 마지막 행의 dp 값 중 최소값이 정답입니다.

---

아이디어

1. 초기화:
• 첫 번째 행은 arr 값 그대로 초기화 (출발점이므로).


2. DP 점화식 적용:
• i=1 행부터 N-1 행까지,
• 각 칸 (i,j)에 대해 3방향(d)을 따로 계산합니다.
• 같은 방향을 연속으로 사용하지 않도록 k≠d 조건을 적용합니다.


3. 정답 도출:
• 마지막 행(N-1)의 모든 칸과 방향 중 최소값을 출력합니다.

---

전체코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
    int N, M;
    cin >> N >> M;
    int arr[6][6], dp[6][6][3];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++)
            cin >> arr[i][j];
    }
    const int INF = 1000000000;
    int ans = INF;
    // 초기화
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            for (int d = 0; d < 3; d++)
                dp[i][j][d] = INF;
    for (int j = 0; j < M; j++)
        for (int d = 0; d < 3; d++)
            dp[0][j][d] = arr[0][j];
    // DP 갱신
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < M; j++) {
            for (int d = 0; d < 3; d++) {
                int prev;
                if (d == 0) prev = j + 1;
                else if (d == 1) prev = j;
                else prev = j - 1;
                if (prev < 0 || prev >= M) continue;
                for (int k = 0; k < 3; k++) {
                    if (d == k) continue; // 같은 방향 제외
                    if (dp[i - 1][prev][k] == INF) continue;
                    int cur = dp[i - 1][prev][k] + arr[i][j];
                    dp[i][j][d] = min(dp[i][j][d], cur);
                }
            }
        }
    }
    // 마지막 행 최소값 찾기
    for (int j = 0; j < M; j++) {
        for (int d = 0; d < 3; d++) {
            ans = min(ans, dp[N - 1][j][d]);
        }
    }
    cout << ans << endl;
    return 0;
}

---

arr (고정)

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

---

i=0 (초기화: 세 레이어 모두 첫 줄 = arr 0행)

d=0

5 8 5 1
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=1

5 8 5 1
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=2

5 8 5 1
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

---

i=1 (둘째 줄까지 반영: 세 레이어 모두 표시)

arr

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

d=0

5 8 5 1
11 10 9 ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=1

5 8 5 1
8 13 13 5
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=2

5 8 5 1
∞ 10 16 9
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

---

i=2 (셋째 줄까지 반영: 세 레이어 모두 표시)

arr

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

d=0

5 8 5 1
11 10 9 ∞
19 90 70 ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=1

5 8 5 1
8 13 13 5
20 87 74 14
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=2

5 8 5 1
∞ 10 16 9
∞ 85 75 14
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

---

i=3 (넷째 줄부터는: 두 레이어 보여주고 → 남은 1개 레이어의 i=3행만 갱신)

(1) arr, d=1·d=2를 보여주고 → d=0 채우기

arr

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

d=1 (i=2까지 반영 상태)

5 8 5 1
8 13 13 5
20 87 74 14
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=2 (i=2까지 반영 상태)

5 8 5 1
∞ 10 16 9
∞ 85 75 14
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=0 갱신(i=3행만)

5 8 5 1
11 10 9 ∞
19 90 70 ∞
[87 75 19 ∞]
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

---

(2) arr, d=0·d=2를 보여주고 → d=1 채우기

arr

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

d=0 (i=3행까지 반영 상태)

5 8 5 1
11 10 9 ∞
19 90 70 ∞
87 75 19 ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=2 (i=2까지 반영 상태)

5 8 5 1
∞ 10 16 9
∞ 85 75 14
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=1 갱신(i=3행만)

5 8 5 1
8 13 13 5
20 87 74 14
[21 86 75 16]
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

---

(3) arr, d=0·d=1을 보여주고 → d=2 채우기

arr

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

d=0 (i=3행까지 반영 상태)

5 8 5 1
11 10 9 ∞
19 90 70 ∞
87 75 19 ∞
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=1 (i=3행까지 반영 상태)

5 8 5 1
8 13 13 5
20 87 74 14
21 86 75 16
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=2 갱신(i=3행만)

5 8 5 1
∞ 10 16 9
∞ 85 75 14
[∞ 20 92 72]
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

---

i=4

(1) arr, d=1·d=2를 보여주고 → d=0 채우기

arr

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

d=1 (i=3행까지 반영)

5 8 5 1
8 13 13 5
20 87 74 14
21 86 75 16
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=2 (i=3행까지 반영)

5 8 5 1
∞ 10 16 9
∞ 85 75 14
∞ 20 92 72
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=0 갱신(i=4행만)

5 8 5 1
11 10 9 ∞
19 90 70 ∞
87 75 19 ∞
[25 173 17 ∞]
∞ ∞ ∞ ∞

---

(2) arr, d=0·d=2를 보여주고 → d=1 채우기

arr

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

d=0 (i=4행까지 반영)

5 8 5 1
11 10 9 ∞
19 90 70 ∞
87 75 19 ∞
25 173 17 ∞
∞ ∞ ∞ ∞

d=2 (i=3행까지 반영)

5 8 5 1
∞ 10 16 9
∞ 85 75 14
∞ 20 92 72
∞ ∞ ∞ ∞
∞ ∞ ∞ ∞

d=1 갱신(i=4행만)

5 8 5 1
8 13 13 5
20 87 74 14
21 86 75 16
[92 118 20 77]
∞ ∞ ∞ ∞

---

(3) arr, d=0·d=1을 보여주고 → d=2 채우기

arr

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

d=0 (i=4행까지 반영)

5 8 5 1
11 10 9 ∞
19 90 70 ∞
87 75 19 ∞
25 173 17 ∞
∞ ∞ ∞ ∞

d=1 (i=4행까지 반영)

5 8 5 1
8 13 13 5
20 87 74 14
21 86 75 16
92 118 20 77
∞ ∞ ∞ ∞

d=2 갱신(i=4행만)

5 8 5 1
∞ 10 16 9
∞ 85 75 14
∞ 20 92 72
[∞ 119 76 24]
∞ ∞ ∞ ∞

---

i=5

(1) arr, d=1·d=2를 보여주고 → d=0 채우기

arr

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

d=1 (i=4행까지 반영)

5 8 5 1
8 13 13 5
20 87 74 14
21 86 75 16
92 118 20 77
∞ ∞ ∞ ∞

d=2 (i=4행까지 반영)

5 8 5 1
∞ 10 16 9
∞ 85 75 14
∞ 20 92 72
∞ 119 76 24
∞ ∞ ∞ ∞

d=0 갱신(i=5행만)

5 8 5 1
11 10 9 ∞
19 90 70 ∞
87 75 19 ∞
25 173 17 ∞
[122 115 91 ∞]

---

(2) arr, d=0·d=2를 보여주고 → d=1 채우기

arr

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

d=0 (i=5행까지 반영)

5 8 5 1
11 10 9 ∞
19 90 70 ∞
87 75 19 ∞
25 173 17 ∞
122 115 91 ∞

d=2 (i=4행까지 반영)

5 8 5 1
∞ 10 16 9
∞ 85 75 14
∞ 20 92 72
∞ 119 76 24
∞ ∞ ∞ ∞

d=1 갱신(i=5행만)

5 8 5 1
8 13 13 5
20 87 74 14
21 86 75 16
92 118 20 77
[29 214 84 82]

---

(3) arr, d=0·d=1을 보여주고 → d=2 채우기

arr

5 8 5 1
3 5 8 4
9 77 65 5
2 1 5 2
5 98 1 5
4 95 67 58

d=0 (i=5행까지 반영)

5 8 5 1
11 10 9 ∞
19 90 70 ∞
87 75 19 ∞
25 173 17 ∞
122 115 91 ∞

d=1 (i=5행까지 반영)

5 8 5 1
8 13 13 5
20 87 74 14
21 86 75 16
92 118 20 77
29 214 84 82

d=2 갱신(i=5행만)

5 8 5 1
∞ 10 16 9
∞ 85 75 14
∞ 20 92 72
∞ 119 76 24
[∞ 120 185 75]

---

(참고) 마지막 행에서 최소 선택 (최종 답 = 29)

• 열0: min(122, 29, ∞) = 29
• 열1: min(115, 214, 120) = 115
• 열2: min(91, 84, 185) = 84
• 열3: min(∞, 82, 75) = 75

→ 전체 최소 = 29입니다.

---

결론

• 3차원 DP 배열을 사용하여 각 칸, 각 방향의 최소 연료를 모두 저장하면서 진행합니다.
• 핵심은 같은 방향으로 연속 이동 금지 조건을 \(k \neq d\)로 처리하는 것입니다.
• 마지막 행의 모든 dp값 중 최솟값을 정답으로 출력하면 문제 해결이 가능합니다.