[伯俊]149号RGB/Java,Python
Baekjoon Online Judge
algorithm practice
問題をちくじ解く
15.動的計画法1
いくつかの基礎的な動的計画法の問題を解いてみましょう.
Java/Python
5.RGB距離
1149号
i 1番目の家をそれぞれ異なる色に塗る場合は、1番目からi番目の家を塗る最小コストで局所的な問題を定義します.
これは、すべての家屋のペンキコストの最大値を求める問題であり、各家屋の最大値とすべての経路の最大値を求めるのではなく、最終的に小さな積算値を見つけるための問題である.
1棟あたりの最大値を探して加算するだけでは、初期にコストの低いところを塗り、隣接する家の色を塗り、コストが最も高くなると、最低コストですべて塗ることができないため、すべてのパスの値を比較する必要があります.
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];
}
}
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]))
Reference
この問題について([伯俊]149号RGB/Java,Python), 我々は、より多くの情報をここで見つけました https://velog.io/@jini_eun/백준-1149번-Java-Pythonテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol