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

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

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

DP문제이다. 

아래와 같은 삼각형이 있을때, 위에서 밑으로 내려가는 방향으로 2차원 dp배열을 통해 최대 누적합을 갱신시켜주었다.

그리고, 맨 아래에 있는 누적합 결과중 가장 큰 값을 출력해주었다.

 

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5 

↓

7

10 15

18 16 15

20 25 20 19

24 30 27 25 24     => 제일 큰 누적합은 30

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

int dp[500][500];

int solution(vector<vector<int>> triangle) {
    int answer = 0;
	dp[0][0] = triangle[0][0]; //맨 꼭대기
	int height = triangle.size() - 1;
	for (int i = 0; i < height; i++){ //맨 아래높이의 위까지
		for (int j = 0; j < triangle[i].size(); j++) { //해당 높이의 길이만큼
			for (int k = 0; k < 2; k++) { //왼쪽&오른쪽
				int next = triangle[i+1][j + k];
				dp[i + 1][j + k] = max(dp[i + 1][j + k], dp[i][j] + next); //누적합 큰걸로 업데이트
			}
		}
	}
	for (int i = 0; i < triangle[height].size(); i++){//맨 아래의 값중 가장 큰거
		answer = max(answer, dp[height][i]);
	}
    return answer;
}

int main() {
	cout << solution({ {7},{3, 8},{8, 1, 0},{2, 7, 4, 4},{4, 5, 2, 6, 5 } }) << endl;
}