[백준]1932-정수 삼각형(Dynamic Programming)

또 다른 동적 계획법 문제인 RGB거리와 크게 다르지 않은 문제이다.

RGB거리 문제를 이해할 수 있다면 크게 어렵지 않게 이해할 수 있을 것이다.

https://everyyy.tistory.com/69 <-RGB거리 풀이

//#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
using namespace std;
 
int exMax(int num, pair<int, int>** triangle);
 
int main() {
    int N;
    scanf("%d", &N);
    pair<int, int>** triangle = new pair<int, int>* [N + 1];
    for (int i = 0; i <= N; i++) {
        triangle[i] = new pair<int, int>[N + 1];
        for (int j = 0; j < N + 1; j++)
            triangle[i][j].first = triangle[i][j].second = 0;
 
        for (int j = 1; j <= i; j++) {
            int num;
            scanf("%d", &num);
            triangle[i][j].first = num;
            triangle[i][j].second = num;
        }
    }
    printf("%d\n", exMax(N, triangle));
    for (int i = 0; i <= N; i++)
        delete[] triangle[i];
    delete[] triangle;
}
 
int exMax(int num, pair<int, int>** triangle) {
    for (int i = 1; i <= num; i++)
        for (int j = 1; j <= i; j++)
            triangle[i][j].second += triangle[i - 1][j].second > triangle[i - 1][j - 1].second ? triangle[i - 1][j].second : triangle[i - 1][j - 1].second;
 
    int max = 0;
 
    for (int i = 1; i <= num; i++)
        if (max < triangle[num][i].second)
            max = triangle[num][i].second;
 
    return max;
}