[백준/JAVA] 17404_RGB거리 2

백준🔗

17404번: RGB거리 2

 

문제

 

 

간단 풀이

dp[i][j] : i번째 집을 j색깔(빨강, 초록, 파랑)로 칠하는 데 드는 최소 비용

 

위와 같이 dp 테이블을 정의했고,

i번째 집을 칠할 때는 i-1번째 집과 다른 색으로 칠해야 하기 때문에 dp[i-1]에서 j와 다른 색깔 중 최소 비용에 i번째 집을 j색깔로 칠하는 비용을 더하면서 dp테이블을 채우면 된다.

 

단, 1번 집과 N번 집의 색도 같지 않아야 하기 때문에

경우의 수를 3가지로 나누었다.

1) 첫 번째 집을 빨강으로 칠하는 경우 -> 마지막 집이 초록 or 파랑이어야 함

2) 첫 번째 집을 초록으로 칠하는 경우 -> 마지막 집이 빨강 or 파랑이어야 함

3) 첫 번째 집을 파랑으로 칠하는 경우 -> 마지막 집이 빨강 or 초록이어야 함

 

각각의 경우에 대해 N*3의 dp 배열을 채우는 과정을 한 번씩만 수행해주면 되기 때문에

N*3*3만큼의 시간이 소요될 것이다.

 

코드

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

public class Main {
	static int N, res;
	static int[][] dp, cost;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		cost = new int[N][3];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			cost[i][0] = Integer.parseInt(st.nextToken());
			cost[i][1] = Integer.parseInt(st.nextToken());
			cost[i][2] = Integer.parseInt(st.nextToken());
		}
		dp = new int[N][3];
		// 1) 첫 번째 집을 빨강으로 칠하는 경우
		dp[0][0] = cost[0][0];
		dp[0][1] = 1001;
		dp[0][2] = 1001;
		calculate();
		int res = Math.min(dp[N - 1][1], dp[N - 1][2]);
		// 2) 첫 번째 집을 초록으로 칠하는 경우
		dp[0][0] = 1001;
		dp[0][1] = cost[0][1];
		dp[0][2] = 1001;
		calculate();
		res = Math.min(res, Math.min(dp[N - 1][0], dp[N - 1][2]));
		// 3) 첫 번째 집을 파랑으로 칠하는 경우
		dp[0][0] = 1001;
		dp[0][1] = 1001;
		dp[0][2] = cost[0][2];
		calculate();
		res = Math.min(res, Math.min(dp[N - 1][0], dp[N - 1][1]));
		System.out.println(res);
	}

	static void calculate() {
		for (int r = 1; r < N; r++) {
			for (int c = 0; c < 3; c++) {
				dp[r][c] = cost[r][c] + Math.min(dp[r - 1][(c + 1) % 3], dp[r - 1][(c + 2) % 3]);
			}
		}
	}
}

 

참고 자료