백준 17404 (RGB 거리 2) - java

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

17404번: RGB거리 2

 

문제

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

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

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

유형 : DP

 

접근 방식

• 기존 RGB 거리 와의 차이점은 첫번 째 지점에 있다. 첫번 째 지점과 마지막 지점이 연결된 즉 원의 형태이다.
• 결국 첫번째 지점과 마지막 지점의 색깔이 겹치면 안된다.
  • 중요 관점 : 첫 번째 지점의 색깔을 고정하자
• 즉 3번의 반복문 (첫번째 지점의 색깔 : R , G , B)를 수행하면 된다.
  • 첫번째 지점을 고정한 경우 나머지 지점의 색깔을 쓰레기값(최소를 구하는 문제이기 때문에 최대값)을 넣고 반복문을 수행하자.
  • 2번째 지점부터 n-1번째 지점까지는 기존 RGB 거리의 점화식 처럼 수행하면된다.
    • i ,R -> (i-1)지점 까지의 G, B중의 Min값 + i지점의 R 값
    • i, G -> (i-1)지점 까지의 R, B중의 Min값 + i지점의 G 값
    • i, B -> (i-1)지점 까지의 R, G중의 Min값 + i지점의 B 값
  • n번째 지점
    • 색깔을 고정했기 때문에 다른 방식의 점화식이 필요하다.
      • R로 고정했다 가정
        • n-1 지점 까지의 R + min(n지점의 G , B)
        • n-1 지점 까지의 B + n 지점의 G
        • n-1 지점 까지의 G + n 지점의 B

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int n = 0;
    static int[][] arr;

    static int MAX = 1000 * 1000 + 1;

    public static void main(String[] args) throws Exception {
        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());

        arr = new int[n+1][4];

        for(int i=1;i<=n;i++){
            st = new StringTokenizer(br.readLine());

            for(int j=1;j<=3;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int result = MAX;

        for(int i=1;i<=3;i++){
            result = Math.min(result,search(i));
        }

        System.out.println(result);
    }

    static int search(int num){
        int[][] dp = new int[n+1][4];

        dp[1][num] = arr[1][num];

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

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

        if(num == 1){
            dp[n][1] = Integer.MAX_VALUE;
            dp[n][2] = Math.min(dp[n-1][1] , dp[n-1][3]) + arr[n][2];
            dp[n][3] = Math.min(dp[n-1][1] , dp[n-1][2]) + arr[n][3];
        }else if(num == 2){
            dp[n][1] = Math.min(dp[n-1][2] , dp[n-1][3]) + arr[n][1];
            dp[n][2] = Integer.MAX_VALUE;
            dp[n][3] = Math.min(dp[n-1][1] , dp[n-1][2]) + arr[n][3];
        }else{
            dp[n][1] = Math.min(dp[n-1][2] , dp[n-1][3]) + arr[n][1];
            dp[n][2] = Math.min(dp[n-1][1] , dp[n-1][3]) + arr[n][2];
            dp[n][3] = Integer.MAX_VALUE;
        }


        return Math.min(Math.min(dp[n][1],dp[n][2]),dp[n][3]);
    }
}