[BaekJoon] 1149 RGB 거리 (Java)

🔗 문제 링크

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

📝 문제 설명

해당 문제는 N번째 집의 색은 N-1번째 집과 N+1번째 집의 색과 겹치지 않기만 하면 되기에 간단한 Dynamic Programming으로 풀 수 있다.

문제 풀이는 다음과 같다. 앞서 말했듯이 N번째 집은 N-1번째 집의 색과 겹치지 않으면 되기에 dp배열에는 자신과 같은 집을 제외한 이전까지 집을 칠할 때의 최소한의 비용+자기 자신의 집을 칠할 때의 비용의 합을 구하여 각각의 dp배열을 채워주면 된다.

이러한 풀이를 하면 배열의 끝의 RGB값들 중 최솟값이 최종 결과가 된다.

👨🏻‍💻 작성한 코드

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

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		int[][] info = new int[N][3];
		int[][] dp = new int[N][3];
		
		for (int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int j=0; j<3; j++) {
				info[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 첫번쨰 집의 정보 추가
		for (int j=0; j<3; j++) dp[0][j] = info[0][j];
		
		// 두번째 이후의 집 dp 계산
		for (int i=1; i<N; i++) {
			dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + info[i][0];
			dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + info[i][1];
			dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + info[i][2];
		}
		
		// 모든 집을 칠했을 때 가장 적은 비용 구하기
		int min = Integer.MAX_VALUE;
		for (int i=0; i<3; i++) {
			if(dp[N-1][i] < min) min = dp[N-1][i];
		}
		
		System.out.println(min);
	}

}