[伯俊]149号RGB/Java,Python


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]))