백준 1149 RGB 거리 (JAVA 자바 풀이)

백준 1149 RGB 거리 (JAVA 자바 풀이)

 

---

 

 

📌 문제 

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

 

 

⚔ 입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

 

📣 출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

 

 

 

 

---

 

 

 

💎 문제 분석

 

 

N의 최대값이 10,000,000에 시간제한은 1초이므로 반복문을 사용하면 100% 시간 초과가 날 것이고 

일일히 구하는 것이 아니라 숫자를 줄여나가면서 구하면서 출력하는 방식으로 풀어야 한다. 

 

 

💡 코드 구현

 

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

public class Main {

	private static int numberOfHouses;
	private static int[][] houses;
	private static int[][] dp;

	public static void main(String[] args) throws IOException {

		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

		numberOfHouses = Integer.parseInt(bufferedReader.readLine());

		houses = new int[numberOfHouses][numberOfHouses];
		for (int i = 0; i < numberOfHouses; i++) {
			StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
			houses[i][0] = Integer.parseInt(stringTokenizer.nextToken());
			houses[i][1] = Integer.parseInt(stringTokenizer.nextToken());
			houses[i][2] = Integer.parseInt(stringTokenizer.nextToken());
		}

		dp = new int[numberOfHouses][3];
		dp[0][0] = houses[0][0];
		dp[0][1] = houses[0][1];
		dp[0][2] = houses[0][2];
		colorRGB();
		System.out.println(findMin(numberOfHouses));
	}

	private static void colorRGB() {
		for (int i = 1; i < numberOfHouses; i++) {
			dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + houses[i][0];
			dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + houses[i][1];
			dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + houses[i][2];
		}
	}

	private static int findMin(int number) {
		int min = dp[number-1][0];
		for (int i = 1; i < 3; i++) {
			if (dp[number-1][i] < min) {
				min = dp[number-1][i];
			}
		}
		return min;
	}
}