백준 1149 RGB거리 - JAVA

1149 문제 링크

---

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

 

문제 설명

---

 

입출력

---

 

코드

---

import java.io.*;
import java.util.*;
 
public class Main {
    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 input = Integer.parseInt(br.readLine());
        int[][] cost = new int[input][3];
        for(int i = 0; i < input; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < 3; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int answer = leastSum(input, cost);
 
        bw.write(String.valueOf(answer));
        bw.flush();
    }
    
    private static int leastSum(int input, int[][] cost) {
        int[][] sum = new int[input][3];
        sum[0] = cost[0];
        
        for(int i = 1; i < input; i++) {
            int[] pres = cost[i];
            sum[i][0] = pres[0] + Math.min(sum[i-1][1], sum[i-1][2]);
            sum[i][1] = pres[1] + Math.min(sum[i-1][0], sum[i-1][2]);
            sum[i][2] = pres[2] + Math.min(sum[i-1][0], sum[i-1][1]);
        }
        
        return Math.min(Math.min(sum[input - 1][0], sum[input - 1][1]), sum[input - 1][2]);
    }
}

 

알고리즘 설명

---

주어진 조건 처럼 인접하는 집의 색은 겹치지 않으면서, 모든 집을 칠하는 최소의 비용을 찾기 위해서 모든 경우의 수를 돌게 된다면,
집의 수가 늘어남에 따라 비효율적인 탐색방법일 수 밖에 없습니다.
 
최소의 비용이 드는 집의 색을 구하기 위해서는, 메모이제이션이 필수입니다. 첫번째 집의 RGB를 제외하고,
두번째 집부터는 전에 칠한 색과 겹치지 않는 두 개의 색 중에서 최소의 비용이 드는 값을 누적하여 더해가야 합니다.
이 설명이 조금 어렵다면 아래 예제 1 그림을 참고하면 좋을 것 같습니다.

예제 1번의 RGB 색비용 배열(cost 배열)

 

최소비용을 찾는 누적합 배열(sum 배열) 알고리즘

이후, 가장 마지막으로 더해진 배열의 R3, G3, B3 중 최솟값이, 가장 최소의 비용이란것을 알 수 있습니다.
위의 표와 같이, 이전 경우의 수를 배열에 저장하여 다음 계산에 재사용 할 수 있도록 만드는것이 핵심입니다.

 

코드 해석

---

 
RGB 숫자들을 cost라는 2차원배열에 담아주고, leastSum이라는 최소비용을 구하는 함수를 호출합니다.
첫번째 배열을 sum배열에 담아주고, 이후 부터는 위의 표와 같이 sum의 다음 배열에 누적합을 담아줍니다.
누적이 모두 끝나면 sum의 마지막 배열의 3개 원소에서 최솟값을 구해 반환합니다.