[BaekJoon] 1149 RGB거리

1.  문제 링크

2.  문제

요약

• N개의 집을 빨강, 초록, 파랑의 색으로 칠하려고 하는데 각 집에 대해 빨강, 초록, 파랑으로 칠하는 비용이 각각 주어졌을 때 서로 이웃하는 집은 색이 같지 않도록 칠할 때의 최소의 비용을 구하는 문제입니다.
• 입력: 첫 번째 줄에 집의 수 N이 주어지고 그 다음 줄부터 N개의 줄에는 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 차례대로 주어집니다.
• 출력: 모든 집을 칠하는 최소의 비용을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
   static int[][] dp;
   static int[][] cost;
   public int getCost(int house, int color) {
      if(dp[house][color] == 0) {
         if(color == 0) {
            dp[house][color] = Math.min(getCost(house - 1, 1), getCost(house - 1, 2)) + cost[house][color];
         } else if(color == 1) {
            dp[house][color] = Math.min(getCost(house - 1, 0), getCost(house - 1, 2)) + cost[house][color];
         } else if(color == 2) {
            dp[house][color] = Math.min(getCost(house - 1, 0), getCost(house - 1, 1)) + cost[house][color];
         }
      }
      return dp[house][color];
   }
   
   public int getMinCost() {
      dp[0][0] = cost[0][0];
      dp[0][1] = cost[0][1];
      dp[0][2] = cost[0][2];
      int min = Math.min(getCost(dp.length - 1, 0), getCost(dp.length - 1, 1));
      return Math.min(min, getCost(dp.length - 1, 2));
   }
   
   public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      int house_num = Integer.parseInt(br.readLine());
      cost = new int[house_num][3];
      dp = new int[house_num][3];
      for(int i = 0; i < cost.length; i++) {
         String input = br.readLine();
         StringTokenizer st = new StringTokenizer(input);
         cost[i][0] = Integer.parseInt(st.nextToken());
         cost[i][1] = Integer.parseInt(st.nextToken());
         cost[i][2] = Integer.parseInt(st.nextToken());
      }
      br.close();
      Main m = new Main();
      bw.write(m.getMinCost() + "\n");
      bw.flush();
      bw.close();
   }
}

4.  접근

• 집을 house, 해당 집의 색깔을 color라는 변수라고 했을 때 house라는 집에 color라는 색이 칠해져있다면 다음 집에는 color라는 색을 칠할 수 없고 다른 색을 칠해야 하며 그 중에서도 최소의 비용이 드는 색을 칠해야 합니다.
• 위 방법을 통해 점화식 하나를 세울 수 있을 것입니다.
• 각각의 비용을 cost라고 한다면 cost[house][color]는 house라는 집을 color라는 색으로 칠했을 때 드는 비용을 의미합니다.
• 이를 이용하여 표를 그려보면 아래와 같은 표가 나오게 됩니다.

• 위 표를 통해 점화식을 도출할 수 있습니다.
• cost[house][color] = cost[house][color] + min(cost[house - 1][color2], cost[house - 2][color3])
• 위 점화식을 이용하여 Dynamic Programming을 이용해 문제를 해결할 것입니다.

1. 위 표와 같이 cost들을 저장할 dp라는 2차원 정수 배열을 하나 만들고 첫 번째 집에는 정해져있는 빨강, 초록, 파랑의 비용을 넣습니다.
2. 비용을 저장하는 dp라는 배열을 채우기 위해 현재 집의 번호와 칠할 색깔을 인자로 넘겨주고 만약 해당 집의 해당 색깔을 아직 칠하지 않았다면, 즉 배열에서 해당 위치의 값이 0이라면 해당 위치의 비용을 채워줍니다.
3. 비용은 재귀를 이용하여 현재 집의 번호보다 낮은 번호들에서 최소의 비용을 구하고 그 최소비용에 자기 자신의 비용을 더합니다. 즉, 위에서 구한 점화식을 진행합니다.
4. 저희가 구하고자 하는 것은 전체 집을 모두 칠한 경우에 최소비용을 구하는 것이기 때문에 인자로 가장 마지막 집과 색깔을 넘겨주는데 빨강, 초록, 파랑 총 3가지 색깔에 대해서 모두 비용을 구해보고 그 중 가장 작은 값을 출력합니다.