[백준] 1149번 : RGB거리 - 자바(JAVA)

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

1149번: RGB거리

 

문제 해석

RGB거리에는 집이 N개가 존재한다.

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

 

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.

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

 

1번 집의 색은 2번집의 색과 같지 않아야 한다.

N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

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

 

문제 풀이 전 설계

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

2096번: 내려가기

해당 문제와 매우 유사해보입니다.

이미 풀었던 적이 있는 문제이기 때문에 유사한 풀이로 접근했습니다.

 

R을 선택하는 경우에는 다음에 G, B를 선택해야 합니다.

G를 선택하는 경우에는 다음에 R, B를 선택해야 합니다.

B를 선택하는 경우에는 다음에 R, G를 선택해야 합니다.

 

이를 통해 DP [3]을 통해 관리합니다. 0은 R, 1은 G, 2는 B를 의미합니다.

 

이때 다음에 R을 선택하는 경우에는 전에 G 또는 B를 선택한 경우입니다.

DP [0] = Math.min( 직전에 G를 선택한 경우, 직전에 B를 선택한 경우) + 현재 R을 선택하는 경우의 비용으로 찾아가면 됩니다.

 

 

코드

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

public class Main_1149_RGB거리 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] dp = new int[3];
        int[][] RGBInfo = new int[3][N+1];

        StringTokenizer st= null;
        for(int i=1; i<N+1; i++){
            st = new StringTokenizer(br.readLine() , " ");
            RGBInfo[0][i] = Integer.parseInt(st.nextToken());
            RGBInfo[1][i] = Integer.parseInt(st.nextToken());
            RGBInfo[2][i] = Integer.parseInt(st.nextToken());

        }
        
        //초기값 설정
        for(int i=0; i<3; i++){
            dp[i] = RGBInfo[i][1];
        }
        /*
        dp[0] = RGBInfo[0][1];
        dp[1] = RGBInfo[1][1];
        dp[2] = RGBInfo[2][1];
         */
         
         //DP값 갱신 0은 R, 1은 G, 2는 B를 의미합니다.
        int temp0,temp1,temp2;
        for(int i=2; i<N+1; i++){
            temp0 = Math.min(dp[1],dp[2]) + RGBInfo[0][i];
            temp1 = Math.min(dp[0],dp[2]) + RGBInfo[1][i];
            temp2 = Math.min(dp[0],dp[1]) + RGBInfo[2][i];

            dp[0] = temp0;
            dp[1] = temp1;
            dp[2] = temp2;

        }
        
        //dp[0],dp[1],dp[2] 중 최솟값이 결과값
        int result = Math.min(Math.min(dp[0],dp[1]) ,dp[2]);
        System.out.println(result);





    }
}