백준 4883번 [삼각 그래프](C++)-yes6686- 티스토리

백준 문제 풀이: 4883 [삼각 그래프]

---

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

문제 설명:

삼각 그래프가 주어질 때, 왼쪽 상단에서 시작하여 오른쪽 하단으로 이동하는 최소 비용을 계산하는 문제입니다. 이동은 다음과 같은 규칙을 따릅니다:

• 현재 위치에서 바로 아래, 아래 왼쪽 대각선, 아래 오른쪽 대각선으로 이동 가능
• 그래프의 각 노드에는 비용이 적혀 있으며, 이동한 노드의 비용을 합산

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

long long arr[100001][3];
long long dp[100001][3];

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

    int t = 1; // 테스트 케이스 번호

    while (true) {
        int n;
        cin >> n;
        if (n == 0) break; // 입력 종료 조건

        // 그래프 입력
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                cin >> arr[i][j];
            }
        }

        // DP 초기값 설정
        dp[0][0] = arr[0][1];
        dp[0][1] = arr[0][1];
        dp[0][2] = arr[0][1] + arr[0][2];

        // DP 계산
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                if (j == 0) {
                    dp[i][j] = min(dp[i - 1][j], dp[i - 1][j + 1]) + arr[i][j];
                } else if (j == 1) {
                    dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1], dp[i][j - 1] + arr[i][j]});
                } else {
                    dp[i][j] = min({dp[i][j - 1], dp[i - 1][j - 1], dp[i - 1][j]}) + arr[i][j];
                }
            }
        }

        // 결과 출력
        cout << t << ". " << dp[n - 1][1] << '\n';
        t++;
    }

    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 최소 비용 경로를 계산합니다. 현재 위치의 비용을 이전 경로의 최소 비용과 합산하여 최적 해를 찾습니다.
• 점화식:
  • dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + arr[i][0]
  • dp[i][1] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i][0]) + arr[i][1]
  • dp[i][2] = min(dp[i-1][1], dp[i-1][2], dp[i][1]) + arr[i][2]
• 구현 세부사항:
  • 입력 삼각 그래프를 기반으로 DP 배열을 채워나감
  • 최소 비용은 항상 마지막 행의 가운데 노드(dp[n-1][1])에 위치
• 시간 복잡도: O(n)
  • 각 행에 대해 최대 3개의 계산을 수행

---

결과

삼각 그래프에서 최소 비용을 정확히 계산합니다. 동적 프로그래밍을 활용해 효율적으로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!