Baekjoon Online Judge

algorithm practice

-問題を逐次解く

33.動的計画法3

ビットマスクを学習し、ダイナミックプランニング法に適用します.次に,線形ではなく円形からなる問題について議論する.
Java/Python

5.RGB距離2

17404号
RGBの距離の問題、円形の家屋で並べます

今回の問題は、家ごとに赤、緑、青の費用を塗る場合、以下のルールを満たすとともに、すべての家の費用の最高値を求めることです.

Java

import java.io.*;
import java.util.*;

public class Main {
	private static final int INF = 1_000 * 1_000;
	static int N;
	static int[][] house;
	static int[][] dp;
	static int result = INF;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;

		N = Integer.parseInt(br.readLine());
		house = new int[N + 1][3];
		dp = new int[N + 1][3];

		// 입력 값 저장
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 3; j++) {
				house[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		// k = 0 -> RED, 1 -> GREEN, 2 -> BLUE
		for (int k = 0; k < 3; k++) {

			for (int i = 0; i < 3; i++) {
				if (i == k) // RED, GREEN, BLUE 색
					dp[1][i] = house[1][i];
				else // 나머지 INF로 초기화
					dp[1][i] = INF;
			}

			for (int i = 2; i <= N; i++) {
				dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + house[i][0];
				dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + house[i][1];
				dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + house[i][2];
			}

			for (int i = 0; i < 3; i++) {
				if (i != k)
					result = Math.min(result, dp[N][i]);
			}
		}

		bw.write(result + "\n");

		bw.flush();
		bw.close();
		br.close();
	}
}

Python

import sys
input = sys.stdin.readline

N = int(input())
house = [[*map(int, input().split())] for _ in range(N)]
dp = [[0]*3 for _ in range(N)]
result = float('inf')

for k in range(3):
    for i in range(3):
        if k == i:
            dp[0][i] = house[0][i]
        else:
            dp[0][i] = float('inf')

    for i in range(1, N):
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + house[i][0]
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + house[i][1]
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + house[i][2]

    for i in range(3):
        if i != k:
            result = min(result, dp[-1][i])

print(result)