[프로그래머스] (동적계획법) 정수 삼각형 (C++)

정수 삼각형 (Level 3)

문제

전체 문제 보기

코딩테스트 연습 - 정수 삼각형

접근법

이 문제에서 구해야 하는 값은 "삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 값"이다. 주어진 삼각형의 n번째 행을 "삼각형의 꼭대기에서 n번째 까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 값"으로 갱신해 모두 갱신하여 풀 수 있다. 아래와 같은 방법으로 모든 삼각형을 갱신한다.

• 삼각형의 가장 좌측 값은 좌측 상단이 없기 때문에 우측 상단값을 가져와서 자신의 값과 합친다.
• 삼각형의 가장 우측 값은 우측 상단이 없기 때문에 좌측 상단 값을 가져와서 자신의 값과 합친다.
• 그 외에는 좌측 상단 혹은 우측 상단 중 큰 값을 가져와서 자신의 값과 합친다.

그리고 가장 마지막 행에서 가장 큰 값을 반환한다.

 

▲ 1 번행 연산 과정

▲ 1번 행 연산 결과와, 2번행 연산 과정

▲ 2번행 연산 결과. n번행 까지 반복한다.

시간 복잡도

이 방식은 가장 작은 점화식 부터 값을 기록해 나가는 바텀업 방식의 DP 알고리즘이다. 시간 복잡도는 삼각형 높이 \(n\)에 대해서 \(O(n^2)\)으로 다소 시간이 오래 걸리는 알고리즘이지만, 최대 삼각형의 높이가 \(500\) 이고, 실제 전체 삼각형을 갱신하기 위해서는 \(500^2\)회가 아닌 \((500+1)* 250 = 125,250\) 회 연산만 요구되기 때문에 제한시간 내 충분히 계산이 가능하다.

구현

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

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

    for(int i = 1; i < triangle.size(); i++)
    {
        for(int j = 0; j < triangle[i].size(); j++)
        {
            // 왼쪽 끝인 경우, 상단 우측 값을 가져옴.
            if(j == 0)
                triangle[i][j] = triangle[i-1][j] + triangle[i][j];
            // 오른쪽 끝인 경우, 상단 좌측 값을 가져옴
            else if (j == triangle[i-1].size())
                triangle[i][j] = triangle[i-1][j-1] + triangle[i][j];
            // 상단 양쪽 모두 값이 있는 경우 비교
            else   
                triangle[i][j] = max(triangle[i-1][j], triangle[i-1][j-1]) + triangle[i][j];

            // 마지막 줄일 경우 최댓값을 탐색
            if( i == triangle.size() - 1 && answer < triangle[i][j])
                answer = triangle[i][j];
        }        
    }
    return answer;
}