[백준] (1149번) RGB거리 (java)

<문제>

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

<나의 풀이>

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

public class RGB거리_1149 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        final int N = Integer.parseInt(br.readLine());

        int[][] arr = new int[N + 1][3];    // 0번째는 0만 들어가고 시작은 1번째 부터
        int[] values = new int[3];  // R,G,B 3개

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j=0; j<3; j++){   // values  에 값 넣어주기
                values[j] = Integer.parseInt(st.nextToken());
            }
            arr [i][0] = Math.min(arr[i-1][1]+values[0], arr[i-1][2]+values[0]);
            arr [i][1] = Math.min(arr[i-1][0]+values[1], arr[i-1][2]+values[1]);
            arr [i][2] = Math.min(arr[i-1][0]+values[2], arr[i-1][1]+values[2]);
        }
        int min = Integer.MAX_VALUE;
        for (int val : arr[N]){
            min = Math.min(min, val);
        }
        System.out.println(min);
    }
}

<다른 사람의 풀이>

재귀로 푸는 방법을 가져와 보았다.

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;
	
	static int[][] Cost;
	static int[][] DP;
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		Cost = new int[N][3];
		DP = 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());
		}
		
		// DP의 첫번째 값(집)은 각 색상비용의 첫번째 값으로 초기화
		DP[0][Red] = Cost[0][Red];
		DP[0][Green] = Cost[0][Green];
		DP[0][Blue] = Cost[0][Blue];
		
		
		System.out.println(Math.min(Paint_cost(N- 1, Red), Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue))));
	}
	
	static int Paint_cost(int N, int color) {
		
		// 만약 탐색하지 않은 배열이라면
		if(DP[N][color] == 0) {
			
			// color의 색에 따라 이전 집의 서로 다른 색을 재귀호출하여 최솟값과 현재 집의 비용을 더해서 DP에 저장한다
			if(color == Red) {
				DP[N][Red] = Math.min(Paint_cost(N - 1, Green), Paint_cost(N - 1, Blue)) + Cost[N][Red];
			}
			else if(color == Green) {
				DP[N][Green] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Blue)) + Cost[N][Green];
			}
			else {
				DP[N][Blue] = Math.min(Paint_cost(N - 1, Red), Paint_cost(N - 1, Green)) + Cost[N][Blue];
			}
			
		}
		
		return DP[N][color];
	}
}

출처 : https://st-lab.tistory.com/128
언제나 많은 도움을 받고있는 감사한 블로그

<핵심 개념>

DP , 특히 이런 문제 풀 때 조심할 점이 누적합으로 풀 수 있다 생각하면 안된다는 점.

<피드백>

처음으로 1시간만에 내가 스스로 풀어낸 DP문제!
삼주 동안 DP 문제를 꼬박꼬박 한개씩 풀었는데 여지껏 못풀다가
처음으로 풀어냈다. 이 맛에 코딩하지..
DP는 규칙을 찾는 일이 매우매우 중요하니, 모르겠으면 꼭 종이에 끄적끄적 하면서 DP테이블 짜보기.

아무튼 오늘도