[C++] (프로그래머스) 정수 삼각형

 

대회명/문제출처: 프로그래머스
문제 링크: https://programmers.co.kr/learn/courses/30/parts/12263
난이도: ★★☆☆☆

• 문제 분류: 동적 프로그래밍

[문제]

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

 

---

[분석]

너무나도 일반적인 DP 문제이다.

그닥... 생각 사고를 요하지 않는다.

주어진 조건에서 정수 삼각형에는 음수 값이 들어갈 수 없으므로 당연히 맨 마지막 줄의 값들 중 최댓값이 주어진다.

 

표를 채운 뒤 맨 마지막 줄의 값 끼리 비교해 최댓값을 찾는다. 

---

[코드]

#include <string>
#include <vector>
unsigned int val[501][501];
using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    int row=1,col=1;
    for(;row<=triangle.size();row++){
        val[row][1]=triangle[row-1][0]+val[row-1][1];
        for(int c=2;c<row;c++){
            if(val[row-1][c-1]<val[row-1][c]) val[row][c]=val[row-1][c];
            else val[row][c]=val[row-1][c-1];
            val[row][c]+=triangle[row-1][c-1];

        }
        val[row][row]=triangle[row-1][row-1]+val[row-1][row-1];

    }
    answer=val[row-1][1];
    for(col=2;col<=triangle.size();col++){
        if(answer<val[row-1][col]) answer=val[row-1][col];
    }
    return answer;
}