[백준] 1149번: RGB거리 - Java

1. 문제

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

1149번: RGB거리

---

2. 접근 방법 및 유의할 점 

i번째 집의 색은 i-1번째, i+1번째 집과 색이다르다는 말을

i-1번째, i번째, i+1번째 집의 색이 모두 달라야한다라는 말로 이해하지 말아야한다.

예를 들어, "빨 파 빨" 도 가능하다는 뜻이다.

이는 첫 번째 집을 제외한 모든 집이 앞집과 색이 다르다는 조건으로 이해해서 활용하면 좋다.

 

이 힌트를 가지고 문제조건을 생각해보자.

i번째 집을 빨간색으로 칠하려고 한다면,

i - 1번째 집이 파란색 또는 초록색으로 칠했을 때까지의 비용에서 최솟값을 선택한 뒤,

i 번째 집의 빨간색 칠 비용을 더해주면 i 번째 집이 빨간색일 때의 최소비용이 나온다.

 

이렇게 초록색, 파란색 경우에도 계산을 한 뒤, 세 가지 중 가장 최솟값이 정답이 된다.

 

(아래 블로그에서 그림으로 자세하게 설명해주셨습니다. 이해가 힘드신분들은 참고하시면 좋을 것 같습니다.)

https://st-lab.tistory.com/128

---

3. 코드

import java.util.*;
import java.io.*;

public class RGB거리 {

    static int n;
    static int[][] cost;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        cost = new int[n][3]; // 각 집의 (RED, GREEN, BLUE) COST

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            cost[i][0] = Integer.parseInt(st.nextToken());
            cost[i][1] = Integer.parseInt(st.nextToken());
            cost[i][2] = Integer.parseInt(st.nextToken());
        }

        solution();
        
        //셋 중 가장 최솟값 선택
        System.out.println(Math.min(Math.min(cost[n-1][0], cost[n-1][1]), cost[n-1][2]));
    }

    // i번째 집까지 칠했을 때 최소 비용은
    // i-1번째 집과 색이 다르면서
    // 최소비용인 경우에 현재 색 비용 추가
    public static void solution() {
        for (int i = 1; i < n; i++) {
            cost[i][0] += Math.min(cost[i-1][1], cost[i-1][2]);
            cost[i][1] += Math.min(cost[i-1][0], cost[i-1][2]);
            cost[i][2] += Math.min(cost[i-1][0], cost[i-1][1]);
        }
    }

}