문제
RGB거리에 N개의 집이 있다. 각 집은 빨강(R), 초록(G), 파랑(B) 중 하나로 칠해야 한다. 조건은 다음과 같다: 1번 집의 색은 2번 집의 색과 같지 않아야 한다, i번 집의 색은 i-1번과 i+1번 집의 색과 달라야 한다, N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. 추가로 1번 집과 N번 집의 색도 달라야 한다. 모든 집을 칠하는 최솟값을 구하라.
입력
첫째 줄에 집의 수 N이 주어진다. (2 ≤ N ≤ 1,000) 둘째 줄부터 N개의 줄에 각 집을 R, G, B로 칠하는 비용이 공백으로 구분되어 주어진다.
출력
모든 집을 칠하는 비용의 최솟값을 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 26 40 83 49 60 57 13 89 99 | 110 |
풀이
1번 집의 시작 색을 고정하고 DP를 3번 반복하여, 마지막 집이 1번 집과 다른 색일 때의 최솟값을 구한다.
- 1번 집의 시작 색 k를 0(R), 1(G), 2(B)로 고정하여 3회 반복한다
- 각 반복에서
dp[1][k] = arr[1][k], 나머지 색은 INF로 초기화한다 - 2번 집부터 N번 집까지 직전 집과 다른 두 색의 최솟값으로 DP 점화식을 적용한다:
dp[i][c] = min(dp[i-1][나머지 두 색]) + arr[i][c] - N번 집에서 k가 아닌 두 색의 DP 값 중 최솟값을 전역 answer와 비교하여 갱신한다
핵심 아이디어: 1번 집의 색을 고정(3가지 경우)함으로써 첫 집과 마지막 집이 다른 색이어야 하는 원형 조건을 일반 DP로 해결한다.
코드
package ASP_study.day299;
import java.io.*;
import java.util.StringTokenizer;
public class Day268BOJ17404RGB거리2 {
private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
private static final int INF = 1_000 * 1_000;
static int n;
static int arr[][];
static int dp[][];
static int answer = INF;
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
arr = new int[n + 1][3];
dp = new int[n + 1][3];
for (int i = 1; i <= n; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int k = 0; k < 3; k++) {
for (int i = 0; i < 3; i++) {
if (i == k)
dp[1][i] = arr[1][i];
else
dp[1][i] = INF;
}
for (int i = 2; i <= n; i++) {
dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2];
}
for (int i = 0; i < 3; i++)
if (i != k)
answer = Math.min(answer, dp[n][i]);
}
bw.write(answer + "\n");
bw.close();
br.close();
}
}복잡도
- 시간: O(N²)
- 공간: O(N)