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)