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

문제

삼각형의 꼭대기에서 바닥까지 대각선 방향/한 칸 오른쪽/한 칸 왼쪽으로 이동하며 거쳐간 숫자의 합이 가장 큰 경우를 찾아 해당 합을 반환한다.

---

접근

• dp 배열을 통해 삼각형의 위에서 2번째 층부터 탐색하며 바로 위층에서 현재 위치로 올 수 있는 두 경로 중 숫자가 더 큰 것을 선택하여 현재 위치의 숫자와 합하여 저장한다.
• 이를 맨 아래층까지 반복하면 맨 아래층에서 가장 큰 값이 삼각형의 꼭대기에서 바닥까지 거쳐간 숫자의 합이 가장 큰 경우에 해당된다.
• 아래 예를 통해 직접 구해보자.

 

주어진 정수 삼각형

 

삼각형의 꼭대기에서 각 위치까지 가는 경로 중 숫자의 합이 가장 큰 경우

 

해당 예시의 경우 30을 반환하게 된다.

---

성공 코드(내 코드)

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0, triangle_height=triangle.size();
    
    for(int i=1; i<triangle_height; i++){
        for(int j=0; j<triangle[i].size(); j++){
            int max=-1;
            if(j-1>=0){
                max=triangle[i-1][j-1];
            }
            if(j<=triangle[i-1].size()-1){
                if(triangle[i-1][j]>max){
                    max=triangle[i-1][j];
                }
            }
            triangle[i][j]+=max;
        }
    }
    answer=*max_element(triangle[triangle_height-1].begin(), triangle[triangle_height-1].end());
    
    return answer;
}

---

후기

각각의 위치에 도달하며 합해지는 값들의 최대값을 저장하는 것이 이 문제의 포인트인 것 같다!