- Published on
- •👁️
RGB거리 2
- Authors
- Name
- River
문제 설명
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
제한사항
- 2 ≤ N ≤ 1,000
- 집을 칠하는 비용은 1,000보다 작거나 같은 자연수
입출력 예
입력
3 26 40 83 49 60 57 13 89 99
출력
110
설명
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
입력
3 1 100 100 100 1 100 100 100 1
출력
3
설명
1번 집: 파랑(100), 2번 집: 초록(1), 3번 집: 빨강(1) = 총 102 하지만 실제로는 다른 조합 존재: 최적해 = 3
입력
3 1 100 100 100 100 100 1 100 100
출력
201
설명
원형 제약으로 인해 1번과 3번 집이 다른 색이어야 함
입력
6 30 19 5 64 77 64 15 19 97 4 71 57 90 86 84 93 32 91
출력
208
설명
6개 집의 최적 색칠 조합을 찾아 최소 비용 208
입력
8 71 39 44 32 83 55 51 37 63 89 29 100 83 58 11 65 13 15 47 25 29 60 66 19
출력
253
설명
8개 집의 최적 색칠 조합을 찾아 최소 비용 253
풀이 접근법
시간복잡도 : O(N)
공간복잡도 : O(N)
사용 알고리즘 :
DP상태제약메모이제이션
핵심 포인트 :
- DP 상태 정의: dp[i][color][firstColor] = i번째 집을 color로 칠하고 첫 집이 firstColor일 때의 최소 비용
- 인접 제약 조건: 현재 집과 이전 집의 색깔이 달라야 함
- 원형 제약 조건: 1번집과 N번집의 색깔이 달라야 함
경계값/반례 :
- 모든 집은 반드시 칠해야 함: 최소 N개의 색칠 비용 발생
- 원형 구조이므로 첫 번째 집 색깔을 고정하고 마지막 집은 다른 색으로만 칠할 수 있음
핵심 아이디어
- 첫 번째 집 색깔을 기억하면서 마지막 집이 첫 집과 다른 색이 되도록 제약
해결 방법
- 3차원 DP로 현재 위치, 현재 색깔, 첫 번째 집 색깔을 모두 관리
- 마지막 집에서 첫 번째 집과 같은 색인 경우 무한대 반환
- 각 첫 번째 집 색깔에 대해 마지막 집을 다른 색으로 칠하는 최소 비용 계산
내부 해부 과정
3
1 100 100
100 1 100
100 100 1
int answer = Math.min(Math.min(dp(n, 1, 1), dp(n, 2, 2)), dp(n, 3, 3));
(빨강) dp(3, 1, 1) = 101 + 100 = 201
- (초록)
dp(2, 2, 1)= 100 + 1 = 101dp(1, 1, 1)- 1번째 집 빨강, 첫 집 빨강 = 무한dp(1, 3, 1)- 1번째 집 파랑, 첫 집 빨강 = 100- 여기 까지 최소 비용 = 100
- (파랑)
dp(2, 3, 1)= 100 + 100 = 200dp(1, 1, 1)- 1번째 집 빨강, 첫 집 빨강 = 무한dp(1, 2, 1)- 1번째 집 초록, 첫 집 빨강 = 100- 여기 까지 최소 비용 = 100
- 여기 까지 최소 비용 = 101
(초록) dp(3, 2, 2) = 101 + 100 = 201
- (빨강)
dp(2, 1, 2)= 100 + 100 = 200dp(1, 2, 2)- 1번째 집 초록, 첫 집 초록 = 무한dp(1, 3, 2)- 1번째 집 파랑, 첫 집 초록 = 100- 여기 까지 최소 비용 = 100
- (파랑)
dp(2, 3, 2)= 1 + 100 = 101dp(1, 1, 2)- 1번째 집 빨강, 첫 집 초록 = 1dp(1, 2, 2)- 1번째 집 초록, 첫 집 초록 = 무한- 여기 까지 최소 비용 = 1
- 여기 까지 최소 비용 = 101
(파랑) dp(3, 3, 3) = 2 + 1 = 3
- (빨강)
dp(2, 1, 3)= 100 + 100 = 200dp(1, 2, 3)- 1번째 집 초록, 첫 집 파랑 = 100dp(1, 3, 3)- 1번째 집 파랑, 첫 집 파랑 = 무한- 여기 까지 최소 비용 = 100
- (초록)
dp(2, 2, 3)= 1 + 1 = 2dp(1, 1, 3)- 1번째 집 빨강, 첫 집 파랑 = 1dp(1, 3, 3)- 1번째 집 파랑, 첫 집 파랑 = 무한- 여기 까지 최소 비용 = 1
- 여기 까지 최소 비용 = 2
핵심 패턴
1️⃣ 원형 제약 DP
static int dp(int num, int color, int nColor) {
if (num == 1) {
if (color == nColor) return 1000000000; // 첫 집과 마지막 집 같은 색
return costs[1][color];
}
if (dp[num][color][nColor] != -1) return dp[num][color][nColor];
int min = 1000000000;
for (int prev = 1; prev <= 3; prev++) {
if (prev == color) continue; // 인접 제약
min = Math.min(min, dp(num - 1, prev, nColor));
}
return dp[num][color][nColor] = costs[num][color] + min;
}
특징:
- 첫 번째 선택을 마지막까지 기억하여 원형 제약 검사
- 3차원 DP로 위치, 현재 선택, 첫 번째 선택을 모두 관리
- 마지막 단계에서 첫 번째 선택과의 충돌 검사
최종 제출 코드
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int[][][] dp;
static int[][] costs;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
costs = new int[n + 1][4];
dp = new int[n + 1][4][4];
for (int i = 1; i <= n; i++) {
costs[i][1] = sc.nextInt();
costs[i][2] = sc.nextInt();
costs[i][3] = sc.nextInt();
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 3; j++) {
Arrays.fill(dp[i][j], -1);
}
}
int answer = Integer.MAX_VALUE;
// 각 첫 번째 집 색깔에 대해 마지막 집을 다른 색으로 칠하는 최소 비용
for (int firstColor = 1; firstColor <= 3; firstColor++) {
for (int lastColor = 1; lastColor <= 3; lastColor++) {
if (firstColor != lastColor) {
// DP 배열 초기화
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 3; j++) {
Arrays.fill(dp[i][j], -1);
}
}
answer = Math.min(answer, dp(n, lastColor, firstColor));
}
}
}
System.out.println(answer);
sc.close();
}
static int dp(int num, int color, int nColor) {
if (num == 1) {
if (color == nColor) return 1000000000;
return costs[1][color];
}
if (dp[num][color][nColor] != -1) return dp[num][color][nColor];
int min = 1000000000;
for (int prev = 1; prev <= 3; prev++) {
if (prev == color) continue;
min = Math.min(min, dp(num - 1, prev, nColor));
}
return dp[num][color][nColor] = costs[num][color] + min;
}
}