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

✏️ 문제 탐색

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

 

각 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어질 때, N개의 집을 어떤 색으로 칠해야 비용이 최소가 되는지 구하라.

단, 인접한 집의 색은 달라야 한다.

✏️ 구현 아이디어

첫 번째 집부터 차례로 색을 정할 때, 이전 집의 색이 다음 집의 색 선택에 영향을 미친다.

이 원리를 이용하여 각 집의 색을 R, G, B로 선택했을 때 비용의 최솟값을 구해보자.

6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91

0행(첫 번째 집):

• 첫 집은 이전 집이 없으므로 각 색을 선택했을 때 최소 비용이 그대로이다.

30

19

5

 

1행(두 번째 집):

• (1, 0)은 (0, 1) 또는 (0, 2) 다음으로 선택될 수 있다.
  19, 5 중 더 적은 비용은 5이므로 최소 비용은 5+64=71
• (1, 1)은 (0, 0) 또는 (0, 2) 다음으로 선택될 수 있다.
  30, 5 중 더 적은 비용은 5이므로 마찬가지로 최소 비용은 5+77=82
• (1, 2)는 (0, 0) 또는 (0, 1) 다음으로 선택될 수 있다.
  30, 19 중 더 적은 비용은 19이므로 최소 비용은 64+19=83

30	19	5
71	82	83

 

2행(세 번째 집):

• 1행에 구해둔 최솟값을 이용해 같은 방식으로 구한다.

...

 

N-1행까지 진행

✏️ 알고리즘

이전에 구해둔 최소 비용을 이용하여 다음에 올 최소 비용을 구할 수 있으므로, DP를 사용하는 것이 적절하다.

✏️ 시간 복잡도

DP는 전체 연산을 한 번씩만 하므로, 시간 복잡도가 O(N)이다.

구해야 할 모든 경우의 수는 (집의 개수)*(색의 개수)이고 집은 최대 1,000개이므로 최대 3,000번의 연산이 이루어진다.

따라서 제한 시간(0.5초) 안에 연산 가능하다.

✏️ 코드 설계

1. 값을 입력받는다.
2. dp()를 통해 각 색을 선택했을 때 얻을 수 있는 최소 비용을 구한다. 
   1. (1행부터 N-1행까지 실행)
   2. 0열이면 이전 행의 1, 2열 중 더 적은 비용을 더해준다.
   3. 1열이면 이전 행의 0, 2열 중 더 적은 비용을 더해준다.
   4. 2열이면 이전 행의 0, 1열 중 더 적은 비용을 더해준다.
3. 마지막 행을 정렬한 다음, 첫 열의 값을 출력한다.

✏️ 정답 코드

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[][] dp;
    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());

        dp = new int[N][3];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<3; j++){
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=1; i<N; i++){
            for(int j=0; j<3; j++){
                dp(i, j);
            }
        }

        Arrays.sort(dp[N-1]);
        System.out.println(dp[N-1][0]);

    }
    static void dp(int x, int y){
        if(y==0){
            //0열이면 이전 행의 1,2열 중 더 적은 비용을 더해줌
            dp[x][y] += Math.min(dp[x-1][1], dp[x-1][2]);
        }else if(y==1){
            //1열이면 이전 행의 0,2열 중 더 적은 비용을 더해줌
            dp[x][y] += Math.min(dp[x-1][0], dp[x-1][2]);
        }else if(y==2){
            //2열이면 이전 행의 0,1열 중 더 적은 비용을 더해줌
            dp[x][y] += Math.min(dp[x-1][0], dp[x-1][1]);
        }
    }

}

✏️ Note

• 이전 문제는 다음 좌표로의 이동 방향을 문제에서 명시해줬었는데, 이번 문제는 스스로 이동 방향을 찾아야 하는 문제였다.
• 한 좌표에 도달하기 위한 경로가 두 가지 뿐이고, 두 경로 중 비용이 최소가 되게 하는 경로를 선택한다는 점이 이전 문제와 같아서 쉽게 풀 수 있었다.