[프로그래머스] 정수 삼각형

문제 링크

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

문제 요약

• 주어진 숫자 피라미드의 꼭대기에서 바닥까지 거친 숫자의 합이 가장 큰 값을 찾는다.

풀이 흐름

• 문제에서 제시된 가운데 정렬 된 숫자 삼각형을 좌측 정렬로 바꾸면
  7
  3 8
  8 1 0
  2 7 4 4
  4 5 2 6 5
  이런 형태가 된다.
  한줄 한줄을 이차원 배열의 행으로, 한 줄에서 각 숫자들을 열로 본다.

• 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능하다.
  현재 위치의 숫자는 대각선 왼쪽 위 숫자에서 대각선 오른쪽 아래로 내려오면 만날 수 있고, 대각선 오른쪽 위에 있는 숫자에서 왼쪽 아래로 내려와도 만날 수 있다.
  현재 위치의 숫자가 i번째 행의 j번째 숫자라면 위에서부터 현재 위치로 올 수 있는 숫자는 i-1번째 행의 j-1번째 숫자, i-1번째 행의 j+1번째 숫자다.

• 현재 triangle[i][j]의 값는 고정이므로 이전까지 어떤 숫자들을 거쳐서 여기까지 왔는지에 따라 전체 숫자 합이 정해진다. 따라서 현재 위치의 숫자가 가질 수 있는 최대 숫자 합을 dp[i][j] 라고 하면
  dp[i][j] = triangle[i][j] + max(dp[i-1][j-1], dp[i-1][j+1])

• 꼭대기에서부터 바닥까지 각 숫자가 가질 수 있는 숫자합 dp를 구한 뒤 바닥에 있는 dp들 중 가장 큰 값을 리턴하면 된다.

---

코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int n = triangle.size();

    int dp[500][500];
    for(int i=0;i<500;i++)
    {
        for(int j=0;j<500;j++)
            dp[i][j] = 0;
    }
    
    dp[0][0] = triangle[0][0];
    
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            int from_left = j > 0 ? dp[i-1][j-1] : 0;
            int from_right = j < i ? dp[i-1][j] : 0;
            dp[i][j] = triangle[i][j] + max(from_left, from_right);
        }
    }
    
    for(int i=0;i<n;i++)
    {
        if(answer < dp[n-1][i])
            answer = dp[n-1][i];
    }
    
    return answer;
}