[백준] 1149번 : RGB거리 / java - DP 문제

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

1149번: RGB거리

 

[ 코드 ] 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	final static int Red = 0;
	final static int Green = 1;
	final static int Blue = 2;
 
	public static void main(String[] args) throws IOException {
 
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
 
		int N = Integer.parseInt(br.readLine());
 
		int[][] Cost = new int[N][3];
 
		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());
 
		}
 
		// 1부터 N-1까지 각 i별 i-1의 서로 다른 색상 중 최솟값을 누적하여 더한다.  
		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(Math.min(Cost[N - 1][Red], Cost[N - 1][Green]), Cost[N - 1][Blue]));
	}
 
}

 

DP 문제를 몇 개 풀어봤지만 이번 문제는 규칙을 찾아 식으로 만들어내는 것이 아닌 경우의 수를 찾아 저장하는 메모이제이션 방식을 취하는 문제였다. 나는 처음에 그리디 방식으로 하나하나 잡아가는 식으로 풀어냈는데, 그 과정에서 이너 클래스를 생성하고, Comparator를 사용하며 다시 익혔다. Comparator나 Comparable을 사용하는 것이 아직도 익숙치가 않아 더 연습이 필요할 것 같다.

밑의 코드는 실패한 코드다.

가장 작은 수를 찾아서 하나하나 경우를 잘라나가다보면 될 줄 알았는데 아니었다...!

반례는 밑의 문제풀이 참고 블로그에 있다.

 

 

[ 실패 코드 ]

 

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

public class Main {
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;

        int N = Integer.parseInt(br.readLine());
        int[][] color = new int[N][3];
        boolean[][] visited = new boolean[N][3];
        ArrayList<Color> list = new ArrayList<>();
        int sum = 0;

        for (int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());

            color[i][0] = Integer.parseInt(st.nextToken());
            color[i][1] = Integer.parseInt(st.nextToken());
            color[i][2] = Integer.parseInt(st.nextToken());

            list.add(new Color(i, 0, color[i][0]));
            list.add(new Color(i, 1, color[i][1]));
            list.add(new Color(i, 2, color[i][2]));
        }

        Collections.sort(list);

        for (int i=0; i<list.size(); i++) {
            Color col = list.get(i);
            int r = col.r;
            int c = col.c;

            if (!visited[r][c]) {
                visited[r][0] = true;
                visited[r][1] = true;
                visited[r][2] = true;

                if (r > 0 && r < N-1) {
                    visited[r-1][c] = true;
                    visited[r+1][c] = true;
                } else if (r == 0) {
                    visited[r+1][c] = true;
                } else if (r == N-1) {
                    visited[r-1][c] = true;
                }

                sum += color[r][c];
            }
        }

        System.out.println(sum);
	}

    static class Color implements Comparable<Color> {
        int r;
        int c;
        int price;

        public Color(int r, int c, int price) {
            this.r = r;
            this.c = c;
            this.price = price;
        }

        @Override
        public int compareTo (Color color) {
            if (color.price < price) {
                return 1;
            } else if (color.price > price) {
                return -1;
            }

            return 0;
        }
    }
}

 

 

※ 오늘의 교훈

DP 문제를 더 풀어보며 익혀야겠다. 메모이제이션 방식을 기억하자.

 

 

 

규칙을 찾아 식으로 만드는 문제 : 1, 2, 3 더하기, 2×n 타일링

경우의 수를 찾아 가장 최적의 경우를 저장하는 문제 : 1로 만들기

 

 

참고 :
문제 풀이 - https://st-lab.tistory.com/128

Java this 개념 - https://library1008.tistory.com/4

사용자 정의 class ArrayList 정렬 (Comparator 사용) - https://hianna.tistory.com/569​