[Baekjoon] 1932번: 정수 삼각형

🥅 문제

https://www.acmicpc.net/problem/1932

 

🔍 설계

어떤 수까지의 경로 상의 합은 맨 위부터 왼쪽 아래, 오른쪽 아래를 계속 선택하여 얻어지므로 다이나믹 프로그래밍을 이용한다. 일차원 배열에 수를 모두 담았을 때, 어떤 수가 n번째 줄에 있다면, 왼쪽 아래에 있는 수는 +n에 있고, 오른쪽 아래에 있는 수는 +(n+1)에 있다.

 

👊 풀이

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

int n, number, k, result;
vector<int> triangle(1, -1);
vector<int> dp(500 * 501 / 2);

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			cin >> number;
			triangle.push_back(number);
		}
	}

	k = 1;
	dp[1] = triangle[1];
	result = dp[1];
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < i; j++) {
			dp[k + i] = max(dp[k + i], dp[k] + triangle[k + i]);
			dp[k + i + 1] = max(dp[k + i + 1], dp[k] + triangle[k + i + 1]);
			result = max(max(result, dp[k + i]), dp[k + i + 1]);
			k++;
		}
	}

	cout << result << "\n";
	
	return 0;
}