프로그래머스 - 정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105

프로그래머스

 이 문제는 전형적인 동적 계획법(dynamic programming) 문제라고 생각한다. 이 문제에서는 삼각형의 꼭대기에서 바닥까지의 경로에 있는 숫자들을 전부 합한 값들 중 최댓값을 구해야 한다. 그렇기에 삼각형의 가장 밑 변의 각각의 경우에서의 최댓값들을 비교하여 답을 구하면 된다. 

1. 삼각형의 높이, 삼각형의 밑변의 길이, 다이나믹 프로그래밍을 위한 변수들 등의 값들을 초기화한다. 특히, 결과를 저장할 배열들은 전부 -1로 설정한다.
2. 삼각형의 가장 밑 변의 숫자들이 도착지라고 가정하였을 때의 최댓값들을 하나씩 비교하면서 답을 찾는다. 이 때, 답을 찾는 과정은 다음과 같다.
   1. 만약 현재 위치가 삼각형의 범위를 벗어난다면 0을 반환한다. (그냥 넘긴다)
   2. 만약 현재 위치가 이미 검사한 위치라 결과가 저장되어 있다면 그 값을 반환한다. (결과를 저장하는 변수의 값이 -1보다 큰 경우)
   3. 현재 위치의 결과를 저장하는 변수의 값을 0으로 설정한 후, 현재 위치에 따라 어느 쪽으로 올라가야 더 큰 값이 나올지 탐색한다.

 이를 코드로 구현한 것은 다음과 같다.

#include <string>
#include <vector>

using namespace std;

#define MAX 501			// 높이의 최댓값이 500이므로 MAX를 501로 설정(0 ~ 500)

int maxR, maxC;			// maxR: 삼각형의 높이, maxC: 삼각형의 밑변의 길이
int check[MAX][MAX];	// dynamic programming의 기록을 위한 배열
vector<vector<int>> t;	// 주어진 triangle을 전역변수로 이용하기 위함

// dynamic programming을 위한 배열 초기화
void Reset_Check() {

    for (int r = 0; r <= maxR; ++r) {

        for (int c = 0; c < t[r].size(); ++c) {

            check[r][c] = -1;
        }
    }
}

int Bigger(int a, int b) {

    if (a > b)
        return a;
    else
        return b;
}

int Find_Max_Val(int r, int c) {

	// 예외 1. 만약 현재 높이가 삼각형의 범위를 벗어나는 경우
    if (r > maxR || r < 0)
        return 0;

	// 예외 2. 삼각형의 가로 위치가 삼각형의 범위를 벗어나는 경우
    if (c > r || c < 0)
        return 0;

	// 이미 검사한 지점인 경우, 검사한 값을 반환
    if (check[r][c] >= 0)
        return check[r][c];

    check[r][c] = t[r][c];

	
    if (c == 0)			// 만약 현재 삼각형의 가장 왼쪽이라면, 바로 윗 칸으로 갈 수 밖에 없다.
        check[r][c] = check[r][c] + Find_Max_Val(r - 1, c);
    else if (c == r)	// 만약 현재 삼각형의 가장 오른쪽이라면, 바로 윗 칸으로 갈 수 밖에 없다.
        check[r][c] = check[r][c] + Find_Max_Val(r - 1, r - 1);
    else				// 그 외의 경우에는 왼쪽 위, 오른족 위로 갈 수 있다.
        check[r][c] = check[r][c] + Bigger(Find_Max_Val(r - 1, c - 1), Find_Max_Val(r - 1, c));

    return check[r][c];
}

int solution(vector<vector<int>> triangle) {
    int answer = -1;

	// 본격적인 계산을 하기 전, 필요한 것들을 세팅한다.
    t = triangle;

    maxR = triangle.size() - 1;
    maxC = triangle[maxR].size() - 1;

    Reset_Check();

    check[0][0] = triangle[0][0];	
    for (int c = 0; c <= maxC; ++c) 
        answer = Bigger(answer, Find_Max_Val(maxR, c));

    return answer;
}