백준 1932번 [정수 삼각형](C++)-yes6686- 티스토리

백준 문제 풀이: 1932 [정수 삼각형]

---

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

문제 설명:

정수 삼각형이 주어졌을 때, 맨 위층에서 시작하여 아래층으로 내려오며 선택된 숫자의 합이 최대가 되는 경로를 구하는 문제입니다. 각 층에서 선택된 숫자는 바로 아래층의 인접한 숫자로만 이동할 수 있습니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

int arr[501][501];
int dp[501][501];

int main() {
    int n;
    cin >> n;

    // 삼각형 배열 입력
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> arr[i][j];
        }
    }

    // DP 초기화 및 계산
    dp[0][0] = arr[0][0];
    int maxAns = 0;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0) {
                dp[i][j] = dp[i - 1][j] + arr[i][j]; // 왼쪽 가장자리
            } else if (j == i) {
                dp[i][j] = dp[i - 1][j - 1] + arr[i][j]; // 오른쪽 가장자리
            } else {
                dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + arr[i][j]; // 중간
            }
            maxAns = max(maxAns, dp[i][j]); // 최대값 갱신
        }
    }

    cout << maxAns << '\n';
    return 0;
}

---

코드 설명

• 핵심 알고리즘: 동적 프로그래밍을 사용하여 각 층에서 최대 합을 계산합니다.
• 점화식:
  • dp[i][j] = dp[i-1][j-1] + arr[i][j] (왼쪽 위에서 오는 경우)
  • dp[i][j] = dp[i-1][j] + arr[i][j] (바로 위에서 오는 경우)
  • 이 두 경우의 최대값을 선택하여 dp 배열에 저장
• 구현 세부사항:
  • 삼각형 배열을 기반으로 DP 배열을 계산
  • 왼쪽 가장자리와 오른쪽 가장자리를 따로 처리
  • 최종 결과는 dp[n-1]의 최대값
• 시간 복잡도: O(n²)
  • 삼각형의 모든 요소를 한 번씩 방문하며 계산

---

결과

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

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