Baekjoon Online Judge

algorithm practice

問題をちくじ解く

15.動的計画法1

いくつかの基礎的な動的計画法の問題を解いてみましょう.
Java/Python

5.RGB距離

1149号
i 1番目の家をそれぞれ異なる色に塗る場合は、1番目からi番目の家を塗る最小コストで局所的な問題を定義します.

これは、すべての家屋のペンキコストの最大値を求める問題であり、各家屋の最大値とすべての経路の最大値を求めるのではなく、最終的に小さな積算値を見つけるための問題である.
1棟あたりの最大値を探して加算するだけでは、初期にコストの低いところを塗り、隣接する家の色を塗り、コストが最も高くなると、最低コストですべて塗ることができないため、すべてのパスの値を比較する必要があります.

Java

Scanner+再帰呼び出しのコードを使用します.

import java.util.Scanner;
 
public class Main {
	
	final static int R = 0;
	final static int G = 1;
	final static int B = 2;
	
	static int[][] Cost;
	static int[][] DP;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
        
		Cost = new int[N][3];
		DP = new int[N][3];
		
		for(int i = 0; i < N; i++) {
			Cost[i][R] = sc.nextInt();
			Cost[i][G] = sc.nextInt();
			Cost[i][B] = sc.nextInt();
		}
		
		// DP의 첫번째 집 - 각 색의 비용의 첫번째 값으로 초기화
		DP[0][R] = Cost[0][R];
		DP[0][G] = Cost[0][G];
		DP[0][B] = Cost[0][B];
		
		System.out.print(Math.min(Paint(N- 1, R), Math.min(Paint(N - 1, G), Paint(N - 1, B))));
		sc.close();
    }
	
	static int Paint(int N, int color) {
		
		// 탐색하지 않은 배열의 경우
		if(DP[N][color] == 0) {
			
			// color의 색에 따라 이전 집의 서로 다른 색을 재귀호출 
			// 최솟값과 현재 집의 비용을 더해서 DP에 저장
			if(color == R) {
				DP[N][R] = Math.min(Paint(N - 1, G), Paint(N - 1, B)) + Cost[N][R];
			}
			else if(color == G) {
				DP[N][G] = Math.min(Paint(N - 1, R), Paint(N - 1, B)) + Cost[N][G];
			}
			else {
				DP[N][B] = Math.min(Paint(N - 1, R), Paint(N - 1, G)) + Cost[N][B];
			}
		}	
		return DP[N][color];
	}
}

Python

Pythonの場合、これは重複文を使用するコードです.

import sys
N = int(sys.stdin.readline())
P = []
for i in range(N):
    P.append(list(map(int, sys.stdin.readline().split())))
for i in range(1, len(P)):    # 0, 1, 2 = R, G, B
    P[i][0] = min(P[i - 1][1], P[i - 1][2]) + P[i][0]
    P[i][1] = min(P[i - 1][0], P[i - 1][2]) + P[i][1]
    P[i][2] = min(P[i - 1][0], P[i - 1][1]) + P[i][2]
print(min(P[N - 1][0], P[N - 1][1], P[N - 1][2]))