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

RGB 거리

다른 프로젝트로 바빠서 한동안 포스팅을 하지 못했다.

프로젝트가 거의 마무리되었기 때문에 다시 포스팅을 시작해보려 한다.

한동안 쉬었기때문에 이번에는 간단한 문제를 풀이해 보았다.

풀이

문제 설명은 링크를 들어가서 읽어보면 되고 문제를 풀 때 핵심은 바로 앞의 집과 색이 달라야 한다는 것이다.

그래서 처음에는 바로 앞집과 색이 다르면서 비용이 최소인 색을 선택해 답을 구했다. 그렇게 구하면 문제에서 주어진 예시는 통과하지만 시작하자마자 반례에 걸린다.

문제를 해결하는데 쓰인 반례는 아래와 같다.

3
1 2 3
3 2 1
4 5 2
Answer : 5 / WA : 6

처음에 생각한 알고리즘으로 위의 예시를 입력하면 6을 출력한다. 하지만 답은 5이기 때문에 알고리즘을 수정해야한다.

위의 예에서 비용이 최소가 되기 위해서는 1->2->2와 같고 답을 구하기 위해서는 dp를 써야한다.

입력으로 주어진 배열과 똑같은 dp 배열을 만들고 dp의 0번째 행은 주어진 배열의 0번째 행과 똑같이 한다.

그리고 1번째 행부터 계산을 시작하는데 3중 for문을 사용했다. 열이 rgb 3개이기 때문에 시간복잡도에 그렇게 치명적이지 않다고 생각했기 때문이다.

첫 for문은 행을 탐색하고 두번째 for문은 열을 탐색한다. 그리고 3번째 for문은 앞에 선택한 색상과 겹치지 않게 하기 위해서 사용했다.

이제 반복문을 돌면서 이전에 선택한 색상이 아니면 즉, 열이 다르다면 해당 색상을 선택할 수 있다는 것이고 현재 칠하려는 집의 비용은 현재 비용과 선택한 색상의 비용 + 이전에 칠했던 집의 누적 비용과 같다.

말로 설명하니 이해가 잘 안간다. 그래서 주석을 통해 코드로 이해하자.

코드

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

public class Main {
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};

    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 n = Integer.parseInt(br.readLine());
        int[][] cost = new int[n][3];

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < line.length; j++) {
                cost[i][j] = Integer.parseInt(line[j]);
            }
        }

        int answer = 0;
        int[][] dp = new int[n][3];
        // 최소 비교를 위해 dp의 모든 값을 max_value로 채움
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i][j] = Integer.MAX_VALUE;
            }
        }
        //첫 행 복사
        for (int i = 0; i < 3; i++)
            dp[0][i] = cost[0][i];

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                for (int k = 0; k < 3; k++) {
                    if(j != k) {
                 	//현재 칠하려는 집의 위치는 이전에 칠했던 집까지의 누적 비용 + 비용과 현재 칠하려는 집의 누적 비용 중 최소이다.
                        dp[i][j] = Math.min(cost[i][j] + dp[i - 1][k], dp[i][j]);
                    }
                }
            }
        }

        for(int i = 0;i<n;i++){
            for(int j =0;j<3;j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.println();
        }


        answer = Arrays.stream(dp[n - 1]).min().getAsInt();

        bw.write(answer + "\n");
        br.close();
        bw.close();
    }

}