[BOJ]149 RGB距離(Java)
13295 ワード
https://www.acmicpc.net/problem/1149
アルゴリズム#アルゴリズム#
DP
に答える
コード#コード#
import java.io.*;
import java.util.*;
public class Main_1149_RGB거리 {
static int N;
static int[][] RGB, DP;
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
RGB = new int[N][3]; // 각 집마다 RGB로 칠하는 비용을 저장할 배열
DP = new int[N][3]; // 각 집이 Red, Green, Blue로 색칠될 때, 최소값을 저장할 배열
for(int i=0; i<N ;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<3; j++) {
RGB[i][j] = Integer.parseInt(st.nextToken()); // 각 집마다의 RGB 비용 입력
if(i==0) DP[i][j] = RGB[i][j]; // 첫번째 집의 경우 최소값 = 첫번쨰 집을 RGB로 칠하는 비용
}
}
for(int i=1; i<N; i++) { // 두번째 집부터 마지막 집까지 반복
DP[i][0] = Math.min(DP[i-1][1], DP[i-1][2]) + RGB[i][0]; // i번째 집이 R로 칠해질 경우, i-1번째 집이 G, B 로 칠해진 경우 중 최저 비용에 R로 칠할 때의 비용을 더해줌
DP[i][1] = Math.min(DP[i-1][0], DP[i-1][2]) + RGB[i][1]; // i번째 집이 G로 칠해질 경우, i-1번째 집이 R, B 로 칠해진 경우 중 최저 비용에 G로 칠할 때의 비용을 더해줌
DP[i][2] = Math.min(DP[i-1][0], DP[i-1][1]) + RGB[i][2]; // i번째 집이 B로 칠해질 경우, i-1번째 집이 R, G 로 칠해진 경우 중 최저 비용에 B로 칠할 때의 비용을 더해줌
}
Arrays.sort(DP[N-1]); // 마지막 집이 RGB로 칠해진 결과를 정렬
System.out.println(DP[N-1][0]); // 0번째 값 출력(가장 작은값 )
br.close();
}
}
Reference
この問題について([BOJ]149 RGB距離(Java)), 我々は、より多くの情報をここで見つけました https://velog.io/@kimdon17/BOJ-Javaテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol