[백준][JAVA][1149:RGB거리]

✂ 실패한 풀이방법

import java.io.IOException;
import java.util.Scanner;

public class Main {
    public static void main(String args[]) throws IOException{
        Scanner in=new Scanner(System.in);
        int num = in.nextInt();
        int[] colors = new int[num];
        int sum = 0;

        for(int i = 0 ; i < num; i++){
            int r = in.nextInt();
            int g = in.nextInt();
            int b = in.nextInt();

            int leastNum = 0;
            //조건에 맞는 R,G,B 중 한 개의 값을 찾고
            //그 값을 sum에 더하자
            //조건을 먼저 검색하고 값을 넣자(어떤 색이 안될건지 미리 파악!)
            if(i==0){
                //다 가능하니 그냥 최적의 값
                leastNum = Math.min(Math.min(r,g), b);
                if(r == leastNum) colors[0] = 0;
                else if(g == leastNum) colors[0] = 1;
                else if(b == leastNum) colors[0] = 2;
                sum += leastNum;
            }
            else{
                if(colors[i-1] == 0){//이 전의 값 Red
                    leastNum = Math.min(g,b);
                    if(g == leastNum) colors[i] = 1;
                    else if(b == leastNum) colors[i] = 2;
                }
                else if(colors[i-1] == 1){//이 전의 값 Green
                    leastNum = Math.min(r,b);
                    if(r == leastNum) colors[i] = 0;
                    else if(b == leastNum) colors[i] = 2;
                }
                else if(colors[i-1] == 2){//이 전의 값 Blue
                    leastNum = Math.min(r,g);
                    if(r == leastNum) colors[i] = 0;
                    else if(g == leastNum) colors[i] = 1;
                }
                sum += leastNum;
                System.out.println(leastNum);
            }
        }

        System.out.println(sum);
    }
}

예제 입력 4까지는 정상적 값이 나와서 맞췄구나 싶었지만..마지막 예제에서 틀린 값이 나왔다.
DP치고는 문제가 너무 쉽다고 생각하긴 했는데 그 생각이 맞았다.

🔔 풀이법

어떤 방법으로 접근해야할지 생각이 안나서 서칭을 통해 아이디어를 구했다.
내가 틀린 이유도 쉽게 찾을 수 있었는데 나는 단순히 해당 단계에서 최솟값을 찾아서 다음 단계로 이동하는 방식으로 진행했다. 하지만 이렇게 했을 경우에 예시를 나타내겠다!

100 1 100
150 2 150



=> 내 알고리즘 : 1, 150 => 151
=> DP : 100 + 2 => 102

결국 각 단계에서 최솟값을 찾고 다음으로 넘어가는게 아니고 DP를 사용하여 매단계마다의 최적을 기록하면서 가야하는 것이다.. 마치 배낭 문제와 비슷하다는 느낌을 받았다.

💡 알게 된 부분!

DP는 기본적인 메모리즘 기법과 함께 규칙?을 찾아내는 것도 중요하다고 느꼈다. 그리고 그것을 어떻게 풀어내느냐(재귀 등)도 중요한 것 같다.

🎈 올바른 풀이

DP 사용 시 테이블
100 1 100
151 102 151

이러한 형식으로 테이블에 항상 최적의 값이 담기게(현재 집이 빨강이면 빨강값 + 파랑,초록 중 최솟값) 계속 담고 마지막에 담긴 것을 출력하면 끝이다!

https://st-lab.tistory.com/128 님의 블로그가 참 정리가 잘 되어있고 알기도 쉽다.

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]));
	}
 
}