[알고리즘] RGB거리 - 백준

문제

1149번: RGB거리

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Q1149 {
    public static void main(String[] args) throws IOException {
        int[][] houses = input();
        output(houses);
    }

    static int[][] input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] houses = new int[n][3];
        for (int i = 0; i < n; i++) {
            String[] inputStrings = br.readLine().split(" ");
            for (int j = 0; j < 3; j++) {
                houses[i][j] = Integer.parseInt(inputStrings[j]);
            }
        }
        return houses;
    }

    static void output(int[][] houses){
        int n = houses.length;
        int[][] dp = new int[n][3];

        for (int i = 0; i < 3; i++) {
            dp[0][i] = houses[0][i];
        }

        for (int i = 1; i < n; i++) {
            dp[i][0] = houses[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
            dp[i][1] = houses[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
            dp[i][2] = houses[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
        }

        System.out.println(Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])));
    }
}

풀이 방향

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

이 규칙들을 지켜서 집들을 칠한다고 가정할 때 위와 같이 집들의 색칠이 이루어질 것이다.

입력값 받기 - input

static int[][] input() throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    int[][] houses = new int[n][3];
    for (int i = 0; i < n; i++) {
        String[] inputStrings = br.readLine().split(" ");
        for (int j = 0; j < 3; j++) {
            houses[i][j] = Integer.parseInt(inputStrings[j]);
        }
    }
    return houses;
}

먼저 각 집마다 색칠할 때의 입력값들을 받아준다.

houses라는 2차원 정수 배열을 생성한다. 이 배열은 각 집마다 색칠하는 비용을 저장하는 배열이다. 집의 개수는 n이 될 것이고, n개의 집마다 3개의 색으로 집을 색칠할 것이기 때문에 [n][3]의 크기의 정수형 배열을 초기화하여 준다.

그리고 입력한 값들을 정수로 변환하여 배열에 저장한다.

풀이 알고리즘 - output

static void output(int[][] houses){
      int n = houses.length;
      int[][] dp = new int[n][3];

      for (int i = 0; i < 3; i++) {
          dp[0][i] = houses[0][i];
      }

      for (int i = 1; i < n; i++) {
          dp[i][0] = houses[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
          dp[i][1] = houses[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
          dp[i][2] = houses[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
      }

      System.out.println(Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])));
  }
}

문제에서 요구하는 것은 모든 집을 색칠하는 비용의 최솟값을 구하는 것이다.

나의 풀이 방식은 집을 색칠할 때 최솟값을 저장하는 2차원 배열 dp를 초기화하여주는 것이다.

for (int i = 0; i < 3; i++) {
    dp[0][i] = houses[0][i];
}

첫 번째 집은 기존의 색칠 비용이 존재하지 않기 때문에 houses의 첫번째 값과 동일하다.

이를 제외한 dp의 각 배열값들은 다음과 같이 구성될 것이다.

dp의 n번째 값은 n-1까지의 최소비용과 해당 집의 각 색칠에 따른 비용을 저장하게 된다.

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

또한 해당 규칙을 준수하여야 하므로

for (int i = 1; i < n; i++) {
    dp[i][0] = houses[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);
    dp[i][1] = houses[i][1] + Math.min(dp[i - 1][0], dp[i - 1][2]);
    dp[i][2] = houses[i][2] + Math.min(dp[i - 1][0], dp[i - 1][1]);
}

다음과 같이 코드를 작성하였다.

그림에서는 n-1까지의 최소비용이라고 동일하게 작성하였지만, 0번 색깔 즉 해당 집을 빨간색으로 칠할 경우 그 전의 집의 색깔은 그 색깔로 칠하지 않아야 하므로

dp[i][0] = houses[i][0] + Math.min(dp[i - 1][1], dp[i - 1][2]);

다음과 같이 최소 비용이 저장되어야 한다.

이처럼 n번 순회하면서 dp의 값을 채워주면 각 색칠에 따른 집들의 최소 색칠비용들로 dp의 값들이 저장되게 된다.

System.out.println(Math.min(dp[n - 1][0], Math.min(dp[n - 1][1], dp[n - 1][2])));

이후 각 색칠에 따른 최소색칠 비용들을 비교하여 얻은 최솟값이 모든 집을 칠하는 비용의 최솟값이 된다.