[BOJ] 1149: RGB거리(JAVA)

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

1149번: RGB거리

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1 

3

26 40 83

49 60 57

13 89 99

예제 출력 1 

96

 

---

[문제 분석]

시간 제한이 있기 때문에 완전 탐색으로 문제를 해결하게 되면 시간초과가 나게 된다. 따라서 Dynamic programming을 이용하여 해결해야하는 문제이다.

집을 칠하는 최소 비용을 구하는 과정을 다음과 같다.

2차원 배열 cost에 각 집을 칠하는 비용이 r, g, b 순서대로 입력받아 저장되어있다고 하면,

2차원 배열 painting에 최소 비용을 구하는 과정의 비용들이 저장될 것이다.

cost[0][0]	cost[0][1]	cost[0][2]
cost[1][0]	cost[1][1]	cost[1][2]

첫번째 집과 두번째 집을 각각 r, g, b로 칠하는 비용이다.

여기서 두번째 집을 칠할 때 최소비용을 구하는 방법은 다음과 같다.

만약 두번째 집을 빨강으로 칠한다고 하면, 첫번째 집은 초록, 또는 파랑으로 칠해야 한다.

따라서 두번째 집을 빨강으로 칠하는 경우의 최소 비용은 cost[1][0] + min(cost[0][1], cost[0][2]) 로 구할 수 있다.

즉, 두번째 집을 빨강으로 칠하는 비용 + 첫번째 집을 초록 또는 파랑으로 칠하는 비용 중 더 작은 비용 이라고 생각하면 된다.

이 비용은 painting[1][0] = cost[1][0] + min(cost[0][1], cost[0][2]) 에 저장할 것이다.

이를 모든 N번째 집을 칠하는 경우, 즉 painting[N-1][0], painting[N-1][1], painting[N-1][2] 까지 구하고 나면

이 세 개의 값 중 가장 작은 값이 모든 집을 규칙에 맞게 칠한 경우 중 가장 적은 비용이 될 것이다.

 

[코드]

import java.util.*;

public class Main {

    public static void main(String[] args) {
    
      Scanner sc = new Scanner(System.in);
      int N = sc.nextInt();
      int[][] cost = new int[N][3];
      
      for(int i=0;i<N;i++) {
            cost[i][0] = sc.nextInt();
            cost[i][1] = sc.nextInt();
            cost[i][2] = sc.nextInt();
      }
      
      
      int painting[][] = new int[N][3];
      painting[0][0] = cost[0][0];
      painting[0][1] = cost[0][1];
      painting[0][2] = cost[0][2];
      
      for(int i=1;i<N;i++) {
             painting[i][0] = Math.min(painting[i-1][1], painting[i-1][2]) + cost[i][0];
             painting[i][1] = Math.min(painting[i-1][0], painting[i-1][2]) + cost[i][1];
             painting[i][2] = Math.min(painting[i-1][0], painting[i-1][1]) + cost[i][2];
      }


      int min = Integer.MAX_VALUE;
      for(int i=0;i<3;i++) {
           if(min>painting[N-1][i])
                 min=painting[N-1][i];
      }
      System.out.println(min);
      
      
    }
}