[BOJ][JAVA] 1149번, 17404번 : RGB 거리1, RGB 거리2

 

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

1149번: RGB거리

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

17404번: RGB거리 2

 

---

오답노트(푸는 동안 사고과정 및 개선점)

RGB거리는 다음 선택할 게 이전 선택한 걸 제외하고 가장 작은 걸 선택하면 된다.

R -> 이전 G, B 중에 하나를 현재 R에 더한다.

G -> 이전 R, B 중에 하나를 현재 G에 더한다 -> B도 마찬가지로 적용한다.

dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + in[i][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + in[i][1];
dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + in[i][2];

그래서 n번째 dp에서 제일 작은 걸 선택하면 된다. 

이게 RGB거리 1이고 RGB거리 2는 처음 선택한 값을 가지고 가야되는데, 조건이 2개가 필요하다.

1. 처음 선택한 값만 갖고 출발해야되고

2. 최소값을 찾을 대상이 처음선택한 값과 같으면 안된다

for (int j = 0; j < 3; j++) { //
    if (j == c) {
	    dp[1][c] = in[1][c];
	} else {
	    dp[1][j] = 1000000; // 이게 필요한 이유는 아예 큰 값으로 해서 dp[2][]의 경우에 다른 색상이 선택되지않도록 하는 것
	}
}

이때 사용하지않을 시작 지점을 초기화하는 게 중요하다.

처음 Integer.MAX_VALUE로 초기화하면, 밑에서 RGB 거리 1 풀때 사용하던 로직에서 overflow가 발생한다. 그래서 최대값이어서 선택하지않는 게 아니라, -21억이 돼서 최종적으로 -21억이 나와버린다.

---

정답코드

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

public class Main {

	public static void main(String[] args) throws Exception {
		//System.setIn(new FileInputStream("res/boj.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null; // new StringTokenizer(br.readLine(), " ");
		int n = Integer.parseInt(br.readLine());
		int[][] in = new int[n + 1][3];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			in[i][0] = Integer.parseInt(st.nextToken());
			in[i][1] = Integer.parseInt(st.nextToken());
			in[i][2] = Integer.parseInt(st.nextToken());
		}
		// 입력 끝
		int min = 1000000;

		for (int c = 0; c < 3; c++) {
			int[][] dp = new int[n + 1][3];
			dp[1][c] = in[1][c];
			for (int j = 0; j < 3; j++) { //
				if (j == c) {
					dp[1][c] = in[1][c];
				} else {
					dp[1][j] = 1000000; // 이게 필요한 이유는 아예 큰 값으로 해서 dp[2][]의 경우에 다른 색상이 선택되지않도록 하는 것
				}
			}
			for (int i = 2; i <= n; i++) {
				dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + in[i][0];
				dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + in[i][1];
				dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + in[i][2];
			}

			for (int i = 0; i < 3; i++) {
				if (i != c) {
					min = Math.min(min, dp[n][i]);
				}
			}
		}
		System.out.println(min);
	}
}

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^