#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> t) {
int k = t.size() - 1;
reverse(t.begin(), t.end());
for (int i = 0; i < t.size() - 1; i++) {
for (int j = 0; j < k; j++)
t[i + 1][j] = max(t[i][j] + t[i + 1][j], t[i][j + 1] + t[i + 1][j]);
k--;
}
return t[t.size() - 1][0];
}삼각형을 2차원 배열 관점으로 본다면 아래와 같은 모양이 된다.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
규칙 상 삼각형의 맨 위에서 아래로 내려갈 때는 왼쪽 대각선과 오른쪽 대각선 아래로 내려갈 수 있다고 했다.
이 규칙의 뜻은 2차원 배열의 관점으로 봤을 때 현재 인덱스의 [ i + 1 ][ j ] or [ i + 1 ][ j + 1 ] 과 같다.
맨 위 인덱스 [ 0 ][ 0 ]인 7에서 시작할 때 왼쪽 대각선 7 + 3 / 오른쪽 대각선 7 + 8 이고, 그 아래쪽 인덱스 [ 1 ][ 0 ] 인 3에서 시작할 때 왼쪽 대각선 3 + 8 / 오른쪽 대각선 3 + 1 과 같다.
이런 로직으로 Top Down 방식을 이용해 최댓값을 갱신해 나간다면 최종적으로 끝까지 거쳐갔을 때 최댓값을 구할 수 있다.
그러나 Top Down방식으로 계산했을 때 문제점이 있다.
아까 본 인덱스 [ 1 ][ 0 ]인 3에서 시작할 때,
왼쪽 대각선 3 + 8과 오른쪽 대각선 3 + 1을 계산해서 아랫줄 인덱스로 거쳐가는 최댓값을 갱신하지만,
그 다음 단계에서 계산해야 할 인덱스 [ 1 ][ 1 ]을 거쳐가는 경로인 왼쪽 대각선 8 + 1, 오른쪽 대각선 8 + 0 최댓값을 갱신할 때 바로 전 단계에서 계산해놓은 오른쪽 대각선 3 + 1 방향의 인덱스와 겹치게 된다.
이렇게 겹치는 상황이 발생한다면 이전 최댓값을 갱신하기 전 인덱스의 값을 기억 하고 있어야 한다.
그러므로 Top Down 방식보다는 Botton Up 방식을 쓴다면 더 쉽게 해결할 수 있다.
4 5 2 6 5
2 7 4 4
8 1 0
3 8
7
이런 역삼각형이 있다고 해보자. 우리가 찾아야 할 것은 모든 경로를 거쳤을 때 가장 큰 값을 가지는 경로를 찾는 것이다. 이 뜻은 위에서 아래로 가든, 아래에서 위로 가든 어차피 값은 똑같기 때문에 시작 방향은 전혀 상관이 없다. 2차원 배열을 reverse하고 삼각형을 뒤집었다고 가정하자.
아래쪽에서 시작했을 때 로직은 맨 윗줄에서 시작했을 때 -> 4 5 / 5 2 / 2 6 / 6 5 를 가지는 맨 윗줄의 쌍들과 그 쌍들의 왼쪽 대각선 방향을 각각 더한 최댓값만 갱신해주며 역삼각형을 내려간다면, 끝인 7 방향으로 최댓값 계산의 값이 서로 겹치지 않게 최댓값을 갱신하며 내려갈 수 있다.
