1932번 - 정수 삼각형

📌문제

👉 문제보기

코드

2차원 배열 사용

#include <iostream>
#define MAX_SIZE 501
#define MAX(x, y) (x < y ? y : x)

using namespace std;

int dp[MAX_SIZE][MAX_SIZE];

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> dp[i][j];
            if (j == 1) {	// 맨 왼쪽
                dp[i][j] += dp[i - 1][j];
            }
            else if (i == j) { // 맨 오른쪽
                dp[i][j] += dp[i - 1][j - 1];
            }
            else {	// 중간은 둘 중 큰 값 저장
                dp[i][j] += MAX(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
    }
    // DP에 피라미드 형식으로 값이 저장됨
    // 마지막 줄에 있는 최댓값 찾아서 출력
    int ans = dp[n][0];
    for (int i = 1; i <= n; i++) {
        if (ans < dp[n][i]) {
            ans = dp[n][i];
        }
    }
    cout << ans << "\n";

    return 0;
}

1차원 배열 재사용

#include <iostream>
#define MAX_SIZE 501
#define MAX(x, y) (x < y ? y : x)

using namespace std;

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

    int dp[MAX_SIZE];
    int arr[MAX_SIZE];

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> x;
            if (i == 1) {	// 맨 윗줄
                arr[i] = x;
                dp[i] = x;
            }
            else if (j == 1) {	// 맨 왼쪽
                arr[j] = dp[j] + x;
            }
            else if (j == i) {	// 맨 오른쪽
                arr[j] = dp[j - 1] + x;
            }
            else {	// 중앙
                arr[j] = x + MAX(dp[j], dp[j - 1]);
            }
        }
        // 저장된 합을 DP배열에 업데이트
        for (int j = 1; j <= i; j++) {
            dp[j] = arr[j];
        }
    }
    // 배열에 저장된 값 중 최댓값 출력
    int ans = dp[0];
    for (int i = 1; i <= n; i++) {
        if (ans < dp[i]) {
            ans = dp[i];
        }
    }

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

🍳문제 풀이

1. 맨 왼쪽(j == 1)은 바로 윗층의 값과 더한 값
2. 맨 오른쪽(j == i)은 바로 윗층 한칸 전과 더한 값
3. 왼쪽도 오른쪽도 아닌 값은 바로 윗층과 윗층 한칸 적 값 중 큰 값과 더한 값

2차원 배열은 501 * 501크기를 가지므로 메모리가 더 크게 나온다 !

2차원 배열 결과

1차원 배열 결과

중간에 제출 실수로 다시 제출했다..

1차원 배열 DP는 입력 받은 값을 arr배열에 계산하고 dp배열에 업데이트 하는 방법으로 풀었다.
2차원 배열과 원리는 동일하다. 업데이트 하기 전까지는 이전 층의 결과값으로 계산하는 것과 같기 때문.
dp[j]가 업데이트 전까지는 dp[i - 1][j]와 같은 의미.