- Published on
- •👁️
RGB거리
- Authors
- Name
- River
문제 설명
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-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
출력
96
설명
첫째 줄에 집의 수 N이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어진다.
모든 집을 칠하는 비용의 최솟값을 출력한다.
입력
3 1 100 100 100 1 100 100 100 1
출력
3
설명
1번 집: 빨강(1), 2번 집: 초록(1), 3번 집: 빨강(1) = 총 3
입력
3 1 100 100 100 100 100 1 100 100
출력
102
설명
1번 집: 빨강(1), 2번 집: 초록(100), 3번 집: 빨강(1) = 총 102
입력
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] = i번째 집을 color로 칠했을 때의 최소 비용
- 인접 제약 조건: 현재 집과 이전 집의 색깔이 달라야 함
경계값/반례 :
- 모든 집은 반드시 칠해야 함: 최소 N개의 색칠 비용 발생
- N=2일 때는 인접 제약만 고려하면 됨
핵심 아이디어
- 각 집에서 이전 집과 다른 색 중 최소 비용 선택
해결 방법
- 재귀 + 메모이제이션으로 Top-down DP 구현
- 현재 집 색깔과 다른 이전 집 색깔들 중 최소값 선택
핵심 패턴
1️⃣ 상태 제약 DP
// 상태 제약 DP 패턴
static int dp(int pos, int prevChoice) {
if (baseCase) return baseValue;
if (memo[pos][prevChoice] != -1) return memo[pos][prevChoice];
int result = INF;
for (int currentChoice = 0; currentChoice < choices; currentChoice++) {
if (isValid(prevChoice, currentChoice)) { // 제약 조건 체크
result = Math.min(result, dp(pos + 1, currentChoice) + cost[pos][currentChoice]);
}
}
return memo[pos][prevChoice] = result;
}
// RGB거리
static int dp(int num, int color) {
if (num == 1) return costs[1][color];
if (dp[num][color] != -1) return dp[num][color];
int min = 1000000000;
for (int next = 0; next < 3; next++) {
if (next != color) { // 인접한 집과 다른 색깔 조건
min = Math.min(min, dp(num - 1, next));
}
}
return dp[num][color] = costs[num][color] + min;
}
특징
- 이전 상태의 선택이 현재 상태의 선택을 제한
- 2차원 DP로 위치와 선택 정보를 함께 관리
- 제약 조건을 만족하는 경우만 탐색
유사한 패턴 문제들
- 계단 오르기 (연속 3번 같은 발 사용 금지)
- 스티커 (인접한 스티커 선택 금지)
최종 제출 코드
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][3];
dp = new int[n + 1][3];
for (int i = 1; i <= n; i++) {
costs[i][0] = sc.nextInt();
costs[i][1] = sc.nextInt();
costs[i][2] = sc.nextInt();
}
for (int i = 1; i <= n; i++) {
Arrays.fill(dp[i], -1);
}
int answer = Math.min(
Math.min(dp(n, 0), dp(n, 1)),
dp(n, 2)
);
System.out.println(answer);
sc.close();
}
static int dp(int num, int color) {
if (num == 1) return costs[1][color];
if (dp[num][color] != -1) return dp[num][color];
int min = 1000000000;
for (int next = 0; next < 3; next++) {
if (next != color) {
min = Math.min(min, dp(num - 1, next));
}
}
return dp[num][color] = costs[num][color] + min;
}
}