백준 1149 - RGB거리

깃허브:

github.com/MSIQOC/BOJ/blob/master/b1149_RGB%EA%B1%B0%EB%A6%AC.java

 

www.acmicpc.net/problem/1149

1149번: RGB거리

문제의 조건은 다음과 같은데, 해석해보면 한 집과 인접한 집의 색깔은 같지 않아야한다는 뜻이다.

제일 왼쪽이 1번집, 제일 오른쪽이 N번집이다.

 

문제를 봤을 때 i번째 집에서 i-1번째집과 i+1번째 집의 색을 어떻게 칠해야할지 다 고려해봐야할 것 같지만, 사실 위 그림처럼 1번집부터 차례대로 칠해나갈 때 바로 다음집만 다르게 칠하면 조건에 만족하게 된다. 즉, 맨 처음부터 칠해나간다면 i+1번째 집의 색만 다르게 칠하면 되고 i-1번째 집의 색까지 고려할 필요는 없어진다.

결과

이를 풀기 위해서 각 집을 빨강, 파랑, 초록으로 저장하기 위한 가격을 저장해두는 배열 p와 i번째 집을 하나의 색으로 칠했을 때, 거기에 도달할 때 까지의 최소비용을 저장해둔 배열 D를 만들었다. 이차원 배열의 첫번째 원소는 몇번째 집인지를 뜻하고 두번째 원소는 색깔을 뜻한다. (0->빨강, 1->초록, 2->파랑)

첫번째 집을 빨강 초록 파랑으로 칠할 때의 최소 비용은 각 색에 대한 초기비용과 같다.

(0번째를 첫번째집으로 간주했다.)

두번째 집을 최소비용으로 칠하는 경우는 다음과 같이 나뉠 수 있다.

1. 두번째 집이 빨간색인 경우

   -> 첫번째 집을 초록색으로 칠했을 때와 파란색으로 칠했을 때의 가격을 비교해서 더 저렴한걸 구하고 두번째 집을 빨간색으로 칠할 때의 비용을 더해준다.

2. 두번째 집이 초록색인 경우

   -> 첫번째 집을 빨간색으로 칠했을 때와 파란색으로 칠했을 때의 가격을 비교해서 더 저렴한걸 구하고 두번째 집을 초록색으로 칠할 때의 비용을 더해준다.

3. 두번째 집이 파란색인 경우

  -> 첫번째 집을 초록색으로 칠했을 때와 빨간색으로 칠했을 때의 가격을 비교해서 더 저렴한걸 구하고 두번째 집을 파란색으로 칠할 때의 비용을 더해준다.

 

이제 D[1][0], D[1][1], D[1][2]에는 첫번째집을 칠하고 난 뒤 각각 두번째 집을 빨간색으로 칠했을 때의 최소비용, 초록색으로 칠했을 때의 최소비용, 그리고 파란색으로 칠했을 때의 최소비용이 들어있다.

(0을 첫번째로 간주했기 때문에 위에서 D[1][x]에는 두번째 집에 대한 정보가 들어있다.)

 

세번째 집부터는 이제 두번째 집까지 칠했을 때의 최소비용을 이용해서 구할 수 있고 이렇게 반복해서 n번째 집까지 구한 뒤, D[n-1][0], D[n-1][1], D[n-1][2] 중에서 최솟값을 정답으로 출력하면 된다.

//
//  Created by MinSeo on 2021/03/27.
//  Copyright ⓒ 2021 MinSeo Shin. All rights reserved.
//
import java.io.*;
import java.util.*;
public class b1149_RGB거리 {
    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 D[][] = new int[n][3]; //dynamic
        int p[][] = new int[n][3]; //price
        for(int i=0; i<n; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<3; ++j) {
                p[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        D[0][0] = p[0][0];
        D[0][1] = p[0][1];
        D[0][2] = p[0][2];
        for(int i=1; i<n; ++i) {
            for(int j=0; j<3; ++j) {
                if(j==0) 
                    D[i][j] = p[i][j] + Math.min(D[i-1][1], D[i-1][2]); 
                else if(j==1)
                    D[i][j] = p[i][j] + Math.min(D[i-1][0], D[i-1][2]);
                else
                    D[i][j] = p[i][j] + Math.min(D[i-1][0], D[i-1][1]);
            }
        }
        int ans = Integer.MAX_VALUE;
        for(int i=0; i<3; ++i) 
            if(D[n-1][i] < ans) ans = D[n-1][i];
        bw.write(ans+"\n");
        bw.flush();
    }
}