정수 삼각형

• 문제 이해 (백준설명이 별로임; 프로그래머스는 괜찮음)
  : 맨 위에서 가장 아래층까지 내려오는 경로 중 최대 값을 구해라

코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;
// d[i] = i번째 요소에 올때 까지 경로 합의 최대값
int d[502][502]; 
int v[502][502];
int N,MAX=0;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    for(int i=1;i<=N;i++) 
        for(int j=1;j<=i;j++)
            cin >> v[i][j];
    d[1][1] = v[1][1];
    MAX = d[1][1];
    for(int i=2;i<=N;i++)
    {
        for(int j=1;j<=i;j++)
        {
            if(j == 1) {
                d[i][j] = d[i-1][1] + v[i][j];
            }else if(j == i){
                d[i][j] = d[i-1][i-1] + v[i][j];
            }else {
                d[i][j] = max(d[i-1][j-1], d[i-1][j]) + v[i][j];
            }
            MAX = max(d[i][j], MAX);
        }
    }
    cout << MAX;
    return 0;
}

• 풀이
  • 삼각형의 요소를 2차원 배열에 담아서 해결해야 한다
  • 삼각형의 맨 앞 / 중간 / 맨뒤 이렇게 3가지 요소의 종류가 있다고 볼 수 있음
    --> 3개의 점화식이 필요함

• 테이블 정의
  D[i][j] = i층에 있는 j번째 요소에 왔을 때 까지 경로의 최대값
  (2 <= i <= N , 1 <= j <= i)

• 점화식
  1) D[i][1] = D[i-1][1] + v[i][j]; (i == 1) - 맨 앞
  2) D[i][i] = D[i-1][i-1] + v[i][j]; (i == j) - 중간
  3) D[i][j] = max(D[i-1][j-1] , D[i-1][j]) + v[i] [j] - 맨 뒤