[Java Algorithm] RGB 거리 2 BOJ #17404

문제

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

17404번: RGB거리 2

 

내 문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static int n;
	static int[][] r, g, b;
	static int answer = Integer.MAX_VALUE;
	
	public static void first(int red, int green, int blue) {
		for(int i = 0; i < 3; i++) {
			r[0][i] = Integer.MAX_VALUE - 1000;
			g[0][i] = Integer.MAX_VALUE - 1000;
			b[0][i] = Integer.MAX_VALUE - 1000;
		}
		
		r[0][0] = red;
		g[0][1] = green;
		b[0][2] = blue;
	}
	
	public static void middle(int i, int red, int green, int blue) {
		r[i][0] = red + Math.min(r[i-1][1], r[i-1][2]);
		r[i][1] = green + Math.min(r[i-1][0], r[i-1][2]);
		r[i][2] = blue + Math.min(r[i-1][0], r[i-1][1]);
		
		g[i][0] = red + Math.min(g[i-1][1], g[i-1][2]);
		g[i][1] = green + Math.min(g[i-1][0], g[i-1][2]);
		g[i][2] = blue + Math.min(g[i-1][0], g[i-1][1]);
		
		b[i][0] = red + Math.min(b[i-1][1], b[i-1][2]);
		b[i][1] = green + Math.min(b[i-1][0], b[i-1][2]);
		b[i][2] = blue + Math.min(b[i-1][0], b[i-1][1]);
		
		if(i == n-1) findAnswer();
	}
	
	public static void findAnswer() {		
		answer = Math.min(answer, Math.min(r[n-1][1], r[n-1][2]));
		answer = Math.min(answer, Math.min(g[n-1][0], g[n-1][2]));
		answer = Math.min(answer, Math.min(b[n-1][0], b[n-1][1]));
		
		System.out.println(answer);
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(in.readLine());
		r = new int[n][3];
		g = new int[n][3];
		b = new int[n][3];
		
		for(int i = 0; i < n; i++) {
			st = new StringTokenizer(in.readLine());
			int red = Integer.parseInt(st.nextToken());
			int green = Integer.parseInt(st.nextToken());
			int blue = Integer.parseInt(st.nextToken());
			
			if(i == 0) { // 첫 번째 집을 각각 빨강, 초록, 파랑으로 픽스해서 생각해주기
				first(red, green, blue);
			} else { // 두 번째 ~ 마지막 집
				middle(i, red, green, blue);
			}
		}
	}
}

👉 DP 문제
이 문제는 RGB 거리 문제와 거의 동일한데, 한 가지 차이점이 있다면,

집을 사이클처럼 생각하여 첫 번째 집과 마지막 집도 같은 색이 되지 못하도록 해야 한다는 것!

 

따라서 r, g, b 2차원 배열을 만들고,

각각 첫 번째 집이 빨간색, 초록색, 파란색인 경우로 픽스해주고 배열을 채워나갔다.

 

두 번째 집 부터는 RGB 거리 문제와 동일하게,

r, g, b 배열이 각각 현재 빨강, 초록, 파랑으로 칠한다는 것을 가정하고

이전 집의 가능한 색 중 가장 최소 비용이 발생하는 색을 선택하는 식으로 해주어야 하므로

첫 번째 집의 픽스 된 색을 제외한 나머지 색의 자리는 모두 Integer.MaxValue로 채웠다.

(-1000을 해준 이유는, 문제에서 주어진 최대 비용이 1000 이므로

MaxValue 값에 새로운 비용을 더하더라도 값이 넘어가서 음수가 되지 않도록 해주기 위함)

 

그리고 마지막 집까지 모두 칠하면,

r, g, b 각각 첫 번째 집을 칠한 색을 제외한 나머지 색 중 최소 값을 골라 결과를 도출했다.

 

✔️ 아래 예제의 결과 도출 과정을 그림으로 설명했다.

3
26 40 83
49 60 57
13 89 99

 

💡 피드백

• RGB 거리 문제를 풀어봤기 때문에 쉽게 풀이가 가능했다.
• 그러나 효율적으로 푼건 아닌것같아서,!!! 다른 풀이들을 보고 공부 해봐야겠당.