[백준][C++] 4883: 삼각 그래프

문제 링크: https://www.acmicpc.net/problem/4883

 

다이나믹 프로그래밍 문제입니다. 행이 최대 10만이기 때문에 완전탐색은 시간이 많이 걸립니다.

dp를 생각해볼 수 있겠는데요

 

첫 행을 좀 신경써줘야 합니다

일단 맨 왼쪽열 노드에서 시작하면 안됩니다. 적당히 INF 값 넣어줍니다. 세 번째 열 노드도 중간에 낄 수 있습니다. 노드 값이 음수가 될 수 있으니 그렇습니다.

그 밑 행들은 in edge 노드 중에 값이 가장 작은걸 고른 뒤 현재노드의 비용을 더해주면 됩니다

#include <bits/stdc++.h>
using namespace std;


typedef long long ll;

const int INF = 987654321;
int arr[100000][3];
ll dp[100000][3];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);

	for (int tt = 1;; ++tt) {
		int n;
		cin >> n;
		if (n == 0) break;

		for (int i = 0; i < n; ++i)
			for (int j = 0; j < 3; ++j)
				cin >> arr[i][j];

		dp[0][0] = INF;
		dp[0][1] = arr[0][1];
		dp[0][2] = dp[0][1] + arr[0][2];

		for (int i = 1; i < n; ++i) {
			dp[i][0] = min(dp[i-1][0], dp[i-1][1]) + arr[i][0];
			dp[i][1] = min({dp[i][0], dp[i-1][0], dp[i-1][1], dp[i-1][2]}) + arr[i][1];
			dp[i][2] = min({dp[i][1], dp[i-1][1], dp[i-1][2]}) + arr[i][2];
		}

		cout << tt << ". " << dp[n-1][1] << '\n';
	}
	
	return 0;
}

푼 사람들 소스를 보니 온라인 알고리즘으로 바꿔놓은 소스가 많네요.