[알고스팟 TRIANGLEPATH] 삼각형 위의 최대 경로 C++

algospot.com/judge/problem/read/TRIANGLEPATH

algospot.com :: TRIANGLEPATH

 

전체 최적해를 구하는 방식을 썼다가 최적 부분 구조를 책으로 이해하고 짠 코드

동적계획법 진짜 어려웠는데 종만북보고 차차 알아가는재미가 너무 좋다

 

 

만약 아래, 오른쪽아래 

둘중 아무 값이나 현재의 값과 더했을때 큰 수를 구할 수 있다면

이를 dp를 이용해서 전체해의 최적값으로 연결지을 수 있다.

 

#include <iostream>
#include <cstring>
#include <algorithm>
 
using namespace std;
int arr[100][100];
int dp[100][100];
int n;
 
//부분 문제의 최적구조를 가지면 전체해도 최적됨
int path(int y, int x) {
    //기저 : 마지막 케이스까지 도달했으면 끝
    if (y == n - 1) return arr[y][x];
    //메모이제이션
    int& ret = dp[y][x];
    if (dp[y][x] != -1) return ret;
 
    //부문문제 두경우중 가장 큰 수
    return ret = max(path(y + 1, x), path(y + 1, x + 1)) + arr[y][x];
}
int main() {
    int c;
 
    cin >> c;
    while (c--) {
        memset(dp, -1, sizeof(dp));
        cin >> n;
        for (int i = 0; i < n; i++)
            for (int j = 0; j <= i; j++)
                cin >> arr[i][j];
        cout << path(0, 0) << '\n';
    }
    return 0;
}