알고리즘/백준
백준 1149 RGB거리 Java [DP]
쫑쫑2
2022. 10. 5. 00:19
https://www.acmicpc.net/problem/1149
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
다이나믹 프로그래밍 문제이다
다음과 같이 예제가 왔을 때
26 40 83
49 60 57
13 89 99
두번째줄의 첫번째 값인 49에 첫번째 줄 두번째 값인 40과 세번째 값 83중 최소값인 40을 더하고
두번째줄의 두번째 값인 60에 첫번째 줄 첫번째 값인 26과 세번째 값 83중 최소값인 26을 더하고
두번째줄의 세번째 값인 57에 첫번째 줄 첫번째 값인 26과 두번째 값 40중 최소값인 26을 더한다
세번째줄부터는 두번째 줄에서 구한 값으로 반복해서 더해주면 된다
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] prev = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int i = 1; i < n; i++) {
int[] now = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
now[0] += Math.min(prev[1], prev[2]);
now[1] += Math.min(prev[0], prev[2]);
now[2] += Math.min(prev[0], prev[1]);
prev = now;
// for (int i = 0; i < 3; i++) {
// now[i] += Math.min(prev[(i+1)%3], prev[(i+2)%3]);
// }
}
System.out.println(Arrays.stream(prev).min().getAsInt());
}
}