[백준 1149번] RGB거리

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

1149번: RGB거리

 

 

1. 어떤 문제로 이해 했는가? 그리고 문제의 제약 조건은?

총 N개의 집이 있고 모든 집은 자신과 이웃한 집들과 색이 겹치지 않아야 한다.

빨, 초, 파로 집을 칠할 수 있고 각 색으로 칠하는 비용이 각 집마다 주어지고

모든 집을 칠하는 최소비용을 구하는 문제이다.

 

집의 갯수는 2<=n<=1000인 자연수이고,

집을 칠하는 비용은 1000보다 같거나 작은 자연수이다.

 

2. 나의 방식대로 문제를 재정의 하자.

각 집의 색 비용을 rgb[][] 배열에 저장한다.

rgb[][0]는 빨간색, rgb[][1]는 초록색, rgb[][2]는 파란색을 저장하고, 

memory[][]배열에 n번째 집이 각 색으로 칠했을 경우 최솟값을 구해

최종적으로 memory[]의 값 중 최솟값을 정답으로 처리한다.

 

 

3. 어떤 알고리즘과 자료구조를 사용할 것인가?

buttom-up방식인 반복문과 top-down 방식인 재귀함수를 활용한다.

 

4. 어떻게 계산할 것인가?

1) 입력

BufferedReader 이용

 

2) 재귀함수

0. 함수 정의 : int calc(int n, int color);

1. 함수의 기능 : n번째 집을 color로 칠하기 위한 최소비용 리턴

2. 반환조건

 - n = 0일경우

       첫번째 집이므로 color에 따라서 해당 색의 비용을 리턴한다.

 - memory[n][color]의 값이 이미 있을 경우

       이미 계산한 값이므로 계산되어져 있는 값 리턴

3. 함수 내부 로직

예를들어 n번째 집을 빨간색으로 칠할 경우, 'n-1번째 집이 초록,파랑색일때의 비용중 더 작은 값' + 'n의 빨간색 비용'이다. 이런 방식으로 n번째 집이 빨간색, 초록색, 파란색일때를 모두 계산해두고 리턴할때는 빨간색만 리턴한다.

 

3) 반복문

재귀함수와 같은 방식으로 진행, memory의 값을 0부터 채워나간다.

 

2) 시간 복잡도 계산

O(n)

 

5. 주의할 점은 무엇인가?

로직을 생각하는 방법이 쉽지 않았다. 재귀함수로 구성할 때 함수의 기능을 확실하게 정의하고 넘어가는것이 핵심

또한 dfs 문제로 볼 수 있으나, 차이점이 무엇인지 생각해봐야함

 

6. 풀이 과정

1) 재귀함수

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


public class q1149 {
    static int[][] memory;
    static int[][] 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));

        Integer N = Integer.parseInt(br.readLine());
        memory = new int[N][3];
        rgb = new int[N][3];

        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            rgb[i][0] = Integer.parseInt(st.nextToken()); //red
            rgb[i][1] = Integer.parseInt(st.nextToken()); //green
            rgb[i][2] = Integer.parseInt(st.nextToken()); //blue
        }

        

        bw.write(Math.min(calc(N-1, 0), Math.min(calc(N-1, 1), calc(N-1, 2)))+ "\n");

        bw.flush();
        br.close();
        bw.close();
    }

    static int calc(int n, int color) {
        if (n == 0) {
            memory[0][0] = rgb[0][0];
            memory[0][1] = rgb[0][1];
            memory[0][2] = rgb[0][2];
            return memory[n][color];
        }

        if (memory[n][color] != 0) {
            return memory[n][color];
        }

        memory[n][0] = Math.min(calc(n - 1, 1), calc(n - 1, 2)) + rgb[n][0];
        memory[n][1] = Math.min(calc(n - 1, 0), calc(n - 1, 2)) + rgb[n][1];
        memory[n][2] = Math.min(calc(n - 1, 0), calc(n - 1, 1)) + rgb[n][2];

        return memory[n][color];
    }

}

일반적인 재귀함수와는 다르게 내부에서 총 3개의 값을 memorization하고있다. 이 부분을 생각하기 어려워서 많은 시간이 걸렸다. 

 

2) 반복문

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


public class q1149 {
    static int[][] memory;
    static int[][] 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));

        Integer N = Integer.parseInt(br.readLine());
        memory = new int[N][3];
        rgb = new int[N][3];

        StringTokenizer st;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            rgb[i][0] = Integer.parseInt(st.nextToken()); //red
            rgb[i][1] = Integer.parseInt(st.nextToken()); //green
            rgb[i][2] = Integer.parseInt(st.nextToken()); //blue
        }

        for (int i = 0; i < N; i++) {
            if (i == 0) {
                memory[0][0] = rgb[0][0];
                memory[0][1] = rgb[0][1];
                memory[0][2] = rgb[0][2];
            }
            else {
                memory[i][0] = Math.min(memory[i - 1][1], memory[i - 1][2]) + rgb[i][0];
                memory[i][1] = Math.min(memory[i - 1][0], memory[i - 1][2]) + rgb[i][1];
                memory[i][2] = Math.min(memory[i - 1][0], memory[i - 1][1]) + rgb[i][2];
            }
        }

        

        bw.write(Math.min(memory[N-1][0], Math.min(memory[N-1][1], memory[N-1][2]))+ "\n");

        bw.flush();
        br.close();
        bw.close();
    }
}

 

 

7. 개선점

dp 문제에서 이차원 배열을 사용할 수도 있다는 점을 기억하는것이 이 문제의 핵심