[알고리즘] C++ 백준 4883 삼각 그래프

백준 4883

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

4883번: 삼각 그래프

풀이 전 나의 생각

이 문제의 요점은 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최소 비용을 구해내는 것이다.

 

조건

1. N은 2보다 같거나 크거나 100000 보다 작거나 같다.

2. 정점의 비용은 정수이며, 비용의 제곱은 1000000보다 작다.

 

문제를 풀기위한 조건은 이와 같다. 여기서 중요한 정보는 정점의 비용이 정수라는 것이다.

(정수: 0을 포함하며 +나 -가 붙은 자연수를 통틀어 말한다.)

정점의 조건 중 수의 제한은 양수 100만 뿐이고 음수에 대한 조건은 없다.

그러므로 음수가 나올 수 있는 상황도 생각하며 점화식을 만들어야 한다.

 

우선 이전값을 탐색하기 위한 초기값을 설정해준다.

 

dp[0][0] = 1000001

가장 위쪽 가운데 정점부터 탐색을 시작하기 때문에 첫 번째 정점은 최대값으로 설정해준다.

 

dp[0][1] = graph[0][1]

첫 시작 부분이기 때문에 그래프의 위쪽 가운데 정점인 (0, 1) 의 위치값을 초기값으로 넣어준다.

 

dp[0][2] = graph[0][1] + graph[0][2]

가장 위쪽 맨 오른쪽 정점의 경우의 수는 가운데 정점에서 오는 경우밖에 없다. 따라서 가장 위쪽 그래프의 중간, 오른쪽 값을 더해준다.

 

이제 초기값을 다 설정했으니 각 정점을 탐색할 때 거쳐야 하는 경우의 수를 적어보자.

 

dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + graph[i][0]

i, 0번째 정점에서 올 수 있는 화살표의 경우의 수를 생각하면된다.

바로 위에 있는 정점에서 내려오는 화살표( dp[i - 1][0] ), 대각선으로 있는 화살표( dp[i - 1][1] ), 이렇게 두 가지 경우에서 최소값을 구하여 현재의 정점값과 더해준다. 

 

dp[i][1] = min({ dp[i - 1][0], dp[i - 1][1], dp[i - 1][2], dp[i][0] }) + graph[i][1]

i, 1번째 정점에서 올 수 있는 화살표의 경우의 수는 좌측 대각선 화살표( dp[i - 1][0] ), 위에 있는 정점에서 내려오는 화살표( dp[i - 1][1] ), 우측 대각선 화살표( dp[i - 1][2] ), 바로 위에 있는 정점에서 좌측 대각선으로 내려와 현재 위치로 오는 화살표( dp[i][0] ), 이렇게 네 가지 경우에서 최소값을 구하여 현재의 정점값과 더해준다. 

 

dp[i][2] = min({ dp[i - 1][1], dp[i - 1][2], dp[i][1] }) + graph[i][2]

i, 2번째 정점에서 올 수 있는 화살표의 경우의 수는 좌측 대각선 화살표( dp[i - 1][1] ), 위에 있는 정점에서 내려오는 화살표( dp[i - 1][2] ), 현재 정점의 좌측에 있는 정점에서 오는 화살표(  dp[i][1] ), 이렇게 세 가지 경우에서 최소값을 구하여 현재의 정점값과 더해준다.

 

최종적으로 정점의 위치에서 올 수 있는 모든 경우의 수를 dp의 점화식으로 나타냈기 때문에 이를 이용하면

각 정점의 최소값을 쉽게 구할 수 있다.

 

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>

int dp[100001][3];
int graph[100001][3];
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n = 0;
	int testCase = 1;
	while (true) {

		cin >> n;
		if (n == 0) break;

		memset(graph, 0, sizeof(graph));

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

		dp[0][0] = 1000001;
		dp[0][1] = graph[0][1];
		dp[0][2] = graph[0][1] + graph[0][2];

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

		cout << testCase << ". "<< dp[n - 1][1] << '\n';
		testCase++;
	}
}