[백준] 4883번 삼각 그래프

1. Approach

 

(1) 다이나믹 프로그래밍으로 접근한다.

 

-> 이유는 (100,00, 3) 의 그래프를 1초 ( 약, 1억번의 연산 ) 내에 전부 탐색하려면 메모이제이션이 반드시 필요하다.

 

(2) DP 배열 정의

 

-> DP[N][4] : N행, 1 - 3 열까지의 정점까지는 오는데에 필요한 최소 비용

 

(3) 풀이 방법

 

-> 아래 그래프와 같이 정점 -> 정점으로 가는 방향은 (아래, 오른쪽, 오른쪽 아래, 왼쪽 아래) 이므로 4가지 방향에 대해서 탐색을 한다.

그래프 범위 내에 있는 경우만 탐색하면된다.

 

(4) 함정

 

-> 마지막으로 입력받는 0이 처음에 입력받는 수열 길이 N을 말하는 것 ( 무한루프 사용으로 해결 )

2. Source Code

#include <iostream>
#include <algorithm>
#include <cstring>
#define MAXINF 987654321
#define MAX 100001
using namespace std;
int n, t;
int graph[MAX][4];		// (1, 1) 부터 시작할 것이다.
int dp[MAX][4];			// idx행, column열까지 가능 최소 비용
/*
	삼각 그래프

	의미 : N 행 3 열로 이루어진 그래프
	목표 : 1행 가운데 정점 -> N행 가운데 정점까지의 최소 비용을 계산

	제약

	1. 간선이 아니라 정점에 비용이 있음 ( 제약(?) 은 아니고 조건 )
*/

// 아래, 오른쪽 아래, 왼쪽 아래, 오른쪽
int dx[] = { 1, 1, 1, 0 };
int dy[] = { 0, 1, -1, 1 };
int solution(int idx, int column)
{
	// 기저 사례
	if (idx > n || column > 3) return MAXINF;

	// 도착
	if (idx == n && column == 2) return graph[n][2];

	int& result = dp[idx][column];
	if (result != -1)
		return result;

	result = MAXINF;
	// 가는 방향이 총 4개 
	for (int k = 0; k < 4; k++)
	{
		int next_x = idx + dx[k];
		int next_y = column + dy[k];

		// 그래프 범위 내에 있는 경우
		if (next_x >= 1 && next_x <= n && next_y >= 1 && next_y <= 3)
		{
			 result = min(result, graph[idx][column] + solution(next_x, next_y));
		}
	}
	return result;
}

int main()
{
	int test_case = 0;
	int onemore;
	while (1)
	{
		cin >> n;
		if (n == 0)
			break;
		// 정점 비용 값을 담아봅시다
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= 3; j++)
				cin >> graph[i][j];

		memset(dp, -1, sizeof(dp));
		cout << ++test_case << ". " << solution(1, 2) << endl;
	}

	return 0;
}

3. 비슷한 문제

1. 다이나믹 프로그래밍 관련 문제

4. 참조

---

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