[백준] 4883번: 삼각 그래프

문제

백준 - 4883번: 삼각 그래프

분석

그림과 같은 삼각 그래프에서 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최소 비용을 구하는 문제이다.
문제에서 말하는 삼각 그래프는 사이클이 없고, N >= 2개의 행과 3열로 이루어져있다.

사이클이 없고 진행되는 노드 마다 각 상태를 가지고 있기 때문에 dp 를 바로 떠올릴 수 있다.
입력에서 비용이 정수이고, 비용의 제곱이 1,000,000보다 작다 했으므로 음수가 올 수도 있다.
그리고 상태의 시작점이 항상 맨 위쪽 가운데 정점이어야 하기 때문에 맨 위쪽 사이드에서 시작되는 경우는 없애야 한다.
시작하는 부분을 보면 2번째 줄까지는 초기화를 잘 생각해야 한다.
먼저, 첫 번째 줄의 왼쪽 노드는 도달할 수가 없다. 따라서 dp에서 이 위치의 값을 쓰면 안 된다.
가운데 노드는 시작점이므로 무조건 비용에 더해야 한다. 따라서 그대로 dp값에 반영한다.
오른쪽 노드는 무조건 가운데에서 온 경우밖에 없다. 따라서 dp[0][j-1]값을 더해준 것으로 초기화한다.
두 번째 줄도 각 경우를 나눠서 생각한다.
왼쪽 노드는 위쪽 가운데에서 오는 경우밖에 없다. 따라서 dp[0][1]값을 더해준다.
나머지 가운데와 오른쪽 노드는 (위쪽 가운데 노드)와 (위쪽 오른쪽 노드) 중에 더 작은 것을 취해서 더해준다. 위쪽 오른쪽 노드는 이미 첫 번째 줄에서 시작점을 거쳐온 것이 보장되므로 이것이 가능하다.
이처럼 초기화만 신경 써서 진행하면 그다음 줄부터는 도달할 수 있는 경우를 생각하여 점화식을 세워주면 된다.

N만큼의 for문이 있고 상수 3은 무시할 수 있기 때문에 한 케이스 당 O(N)이 시간 복잡도이다.

코드

해결언어 : Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N;
	static int[][] arr;
	static int[][] dp;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int tc = 0;
		while (true) {
			tc += 1;
			N = Integer.parseInt(br.readLine());
			if (N == 0)
				break;
			arr = new int[N][3];
			dp = new int[N][3];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine());
				for (int j = 0; j < 3; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			for (int j = 0; j < 3; j++) {
				dp[0][j] = arr[0][j];
				if (j == 2)
					dp[0][j] = dp[0][j - 1] + arr[0][j];
			}
			dp[1][0] = dp[0][1] + arr[1][0];
			dp[1][1] = Math.min(dp[0][1], dp[0][2]) + arr[1][1];
			dp[1][2] = Math.min(dp[0][1], dp[0][2]) + arr[1][2];
			for (int j = 1; j < 3; j++) {
				dp[1][j] = Math.min(dp[1][j], dp[1][j - 1] + arr[1][j]);
			}
			for (int i = 2; i < N; i++) {
				for (int j = 0; j < 3; j++) {
					if (j == 0) {
						dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j + 1]) + arr[i][j];
					} else if (j == 1) {
						dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i - 1][j + 1])) + arr[i][j];
					} else {
						dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + arr[i][j];
					}
					if (j > 0)
						dp[i][j] = Math.min(dp[i][j], dp[i][j - 1] + arr[i][j]);
				}
			}
			sb.append(tc + ".").append(" ");
			sb.append(dp[N - 1][1]);
			sb.append("\n");
		}
		System.out.println(sb);
		br.close();
	}
}