백준 4883번 삼각 그래프 C++

출처 : https://www.acmicpc.net/problem/4883

 

dp테이블을 이용해서 bottom-up 방식으로 해결할 수 있는 문제이다.

주의해야 할 점은 문제의 조건에서 비용의 제곱이 1000000보다 작다고 했기 때문에 음수가 비용으로 들어올 수도 있다는 점이다. 그렇기 때문에 들어오는 모든 경우들을 확인해주어야 한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

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

	int n;
	int cnt = 0;
	while (true) {
		cin >> n;
		if (n == 0) break;
		cnt++;
		vector<vector<int>> v(n, vector<int>(3));
		vector<vector<int>> dp(n, vector<int>(3, 0));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 3; j++) {
				cin >> v[i][j];
			}
		}
		dp[0][1] = v[0][1];
		dp[0][2] = v[0][1] + v[0][2];
		dp[1][0] = v[0][1] + v[1][0];
		dp[1][1] = min(min(dp[0][1], dp[1][0]), dp[0][2]) + v[1][1];
		dp[1][2] = min(min(dp[0][1], dp[1][1]), dp[0][2]) + v[1][2];

		for (int i = 2; i < n; i++) {
			dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + v[i][0];
			dp[i][1] = min(min(min(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]),dp[i][0]) + v[i][1];
			dp[i][2] = min(min(dp[i - 1][1], dp[i - 1][2]),dp[i][1]) + v[i][2];
		}
		cout << cnt << ". " << dp[n - 1][1] << "\n";
	}
};