백준 1149 RGB거리 Java [DP]

https://www.acmicpc.net/problem/1149

1149번: RGB거리

 

다이나믹 프로그래밍 문제이다

 

다음과 같이 예제가 왔을 때

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());
    }
}