백준 17485번 [진우의 달 여행 (Large)](C++) -yes6686- 티스토리

백준 문제 풀이: 17485 [진우의 달 여행 (Large)]

---

문제 링크: https://www.acmicpc.net/problem/17484

문제 설명:

우주선이 지구에서 출발하여 달에 도착할 때까지 연료 소비량이 최소가 되도록 경로를 선택하는 문제입니다.

이동 규칙은 다음과 같습니다:

• 각 행에서는 좌하단(↙), 아래(↓), 우하단(↘)으로만 이동할 수 있습니다.
• 연속해서 같은 방향으로 이동할 수 없습니다.

목표는 (0, x) 위치에서 출발하여 (n-1, y)에 도착하는 최소 연료 소비량을 구하는 것입니다.

---

문제 해결 코드

#include <iostream>
#define INF 1e9
using namespace std;

int arr[1001][1001]; // 각 위치의 연료 소비량
int dp[3][1001][1001]; // 각 방향별 최소 연료 소비량 저장

int dx[3] = { 1, 1, 1 }; // 아래 방향 이동
int dy[3] = { -1, 0, 1 }; // 좌, 아래, 우 이동 방향

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    // 입력 및 DP 배열 초기화
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            for (int h = 0; h < 3; h++) {
                dp[h][i][j] = INF; // 초기값 설정 (최대값)
            }
            if (i == 0) { // 첫 번째 행 초기화 (시작점)
                dp[0][i][j] = arr[i][j];
                dp[1][i][j] = arr[i][j];
                dp[2][i][j] = arr[i][j];
            }
        }
    }

    int minAns = INF;

    // DP 계산
    for (int i = 0; i < n - 1; i++) { // 각 행 탐색
        for (int j = 0; j < m; j++) { // 각 열 탐색
            for (int h = 0; h < 3; h++) { // 이동 방향 선택 (좌, 아래, 우)
                int nx = i + dx[h];
                int ny = j + dy[h];

                if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue; // 범위 초과 방지

                int minFuel;
                if (h == 0) { // 왼쪽에서 내려오는 경우
                    minFuel = min(dp[1][i][j], dp[2][i][j]);
                }
                else if (h == 1) { // 정면에서 내려오는 경우
                    minFuel = min(dp[0][i][j], dp[2][i][j]);
                }
                else { // 오른쪽에서 내려오는 경우
                    minFuel = min(dp[0][i][j], dp[1][i][j]);
                }

                dp[h][nx][ny] = min(dp[h][nx][ny], minFuel + arr[nx][ny]); // 최소 연료 소비량 갱신

                if (i == n - 2) // 마지막 행까지 도달한 경우 최소값 갱신
                    minAns = min(minAns, dp[h][nx][ny]);
            }
        }
    }

    cout << minAns << '\n'; // 최솟값 출력
}

예제 입력:

3 4
1 2 3 4
5 6 7 8
9 10 11 12

예제 출력:

16

---

코드 설명

• 핵심 알고리즘: DP(동적 계획법)을 활용하여 연료 소비량을 최적화합니다.
• 구현 세부사항:
  • 각 칸에서 좌하단(↙), 아래(↓), 우하단(↘) 방향으로만 이동 가능합니다.
  • 연속으로 같은 방향으로 이동할 수 없도록 방향별 최소 연료 소비량을 저장합니다.
  • 현재 칸에 도달하기 위한 최소 연료 값을 DP 배열에 저장하며 최적의 경로를 탐색합니다.
• 시간 복잡도: O(N×M), 모든 칸을 한 번씩 탐색하여 최소 연료 소비량을 계산

---

결과

입력된 연료 소비량을 기준으로 최적의 이동 경로를 계산하여 최소 연료 값을 출력합니다. DP 및 최적화 기법을 연습하기 좋은 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!