[백준] 1149번_RGB거리(Java)

문제 풀이

백준의 1149번 문제입니다. 문제 출처

(1) 문제 파악

(2) 문제 풀이 방법 생각하기

거리에 있는 N개의 집을 색칠하는데 최소 누적합을 구하는 문제입니다.

이때 조건은 인접해 있는 집과는 다른 색상으로 집을 칠해야 한다는 것입니다 현재 위치의 집이 R인 경우 이전 집의 색상은G나 B가 되어야 한다는 뜻이죠!

이때 전체 집을 다 칠한 뒤의 최소 누적합을 구하는 것이므로 각 집의 최소 비용을 더하며 최소 누적합을 구하면 되는 문제입니다.

cost 배열의 초기에는 각 집을 칠할 때 드는 비용으로 초기화한 뒤

\[cost[N][RED] = Math.min(cost[N-1][GREEN], cost[N-1][BLUE]) + cost[N][RED]\] \[cost[N][GREEN] = Math.min(cost[N-1][RED], cost[N-1][BLUE]) + cost[N][GREEN]\] \[cost[N][BLUE] = Math.min(cost[N-1][RED], cost[N-1][GREEN]) + cost[N][BLUE]\]

연산을 수행하고, 최종에서 가장 작은 값을 출력하면 됩니다.

(3) 시간 복잡도 확인

시간 제한은 0.5초 입니다. 즉, 대략 5천만번 연산 안에 문제를 해결해야 합니다.

\[2 <= N <= 1,000\] \[1 <= 집을 칠하는 비용 <= 1,000\]

N까지 fo문을 돌며 cost를 계산하는 연산이 주요 연산이므로, 시간 복잡도는 O(N) 이며, 문제 해결이 가능합니다.

(4) 구현

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

public class Main {
    static final int RED = 0;
    static final int GREEN = 1;
    static final int BLUE = 2;

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

        // 초기화
        StringTokenizer st;
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            cost[i][RED] = Integer.parseInt(st.nextToken());
            cost[i][GREEN] = Integer.parseInt(st.nextToken());
            cost[i][BLUE] = Integer.parseInt(st.nextToken());
        }
        
        for(int i=1; i<N; i++) {
            cost[i][RED] += Math.min(cost[i-1][GREEN], cost[i-1][BLUE]);
            cost[i][GREEN] += Math.min(cost[i-1][RED], cost[i-1][BLUE]);
            cost[i][BLUE] += Math.min(cost[i-1][RED], cost[i-1][GREEN]);
        }

        // 최소 누적합 출력
        System.out.println(Math.min(cost[N-1][BLUE], Math.min(cost[N-1][RED], cost[N-1][GREEN]))); 

        br.close();
    }
}