RGB거리
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
1번 집의 색은 2번 집의 색과 같지 않아야 한다.
N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
입력
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
import sys
sys.stdin = open("input.text", "rt")
input = sys.stdin.readline
n = int(input())
data = []
for _ in range(n):
r,g,b = map(int, input().split())
data.append((r,g,b))
#모든 집을 칠하는 비용의 최솟값
#dp 테이블에는 각 색깔을 칠했을 떄의 최솟값을 저장하자.
dp = [[0] * 3 for _ in range(n)]
dp[0][0] = data[0][0]
dp[0][1] = data[0][1]
dp[0][2] = data[0][2] #자명한건 미리 초기화
for i in range(1,n): #각 색깔별로 구해야.
#현재 j번째 색을 칠할 때, 최솟값을 저장해야 하니까 아래와 같이 작성해야함.
dp[i][0] = min(dp[i-1][1] + data[i][0], dp[i-1][2] + data[i][0])
dp[i][1] = min(dp[i-1][0] + data[i][1], dp[i-1][2] + data[i][1])
dp[i][2] = min(dp[i-1][0] + data[i][2], dp[i-1][1] + data[i][2])
res = min(dp[n-1][0], dp[n-1][1], dp[n-1][2])
print(res)⚽ 코멘트
1~N까지 순서대로 집이 r,g,b값 가지고 있다. 각각의 집을 r,g,b로 칠하는 비용이 주어지면 모든 집을 칠하는 비용의 최솟값...
다이나믹 프로그래밍을 통해 풀어야 한다.
- 앞에서부터 최솟값을 저장해 나가서 모든 집을 칠했을 때의 최솟값을 구했어야 했다.
- 첫번째 집을 제외하고 어떤 RGB 하나를 골르냐에 따라 다음 번 결정에 영향을 끼친다. 그렇기에 그리디로는 풀 수 없고 dp로 풀어야 했따 !
⚽ **처음에 그리디로 풀었는데 매번 최솟값을 택했다. 근데 만약 처음 집에서 최솟값이 아닌 다른 값을 택하더라도 최솟값이 나올 수가 있는 것을 보고 그리디로는 풀 수 없다는 것을 느꼈다.
- 그렇기에 매번 이전까지의 최솟값 + 현재 값을 dp 테이블에 더해나가면서 확인해야 한다는걸 느꼈다.**
먼저 2차원 dp 테이블을 만든 후에 r,g,b를 칠했을 때의 최솟값을 저장한다.
- 예를 들어 dp[n][0]은 현재 n번집에 r페인트를 칠했을 때의 최솟값을 저장하게 된다.
첫 집은 r,g,b 모두 선택할 수 있으므로
dp[0][0]에는 첫번째 집의 r값을, dp[0][1]은 첫번째 집의 g값을, dp[0][2]는 첫번째 집의 b값을 저장하게 된다.
두번째 집부터는 바로 전 집과는 다른 색으로 칠해야 하므로 나머지 색 중에 최솟값을 선택한다.
- 두번째 집에 r을 선택했다면 이전 집에서는 g,b를 칠한 것 중 최솟값을 선택하여 더하면 된다.
이러한 방식으로 값을 누적해 나가며 마지막 집의 dp값을 구하면 답을 구할 수 있다.
체크 포인트
1. 인접한 집끼리는 색이 겹치면 안된다는 점 -> 이 부분에서 그리디는 안된다고 판단
2. 각 집의 최솟값을 찾아 누적합을 구하는 것이 아닌, 모든 경로의 경우의 수를 찾아서 최종적으로 작은 누적합을 찾아야 한다.
3. 점화식을 세울 수 있었어야 했음.
3가지 케이스를 이용해야 하니 -> 2차원 배열로 접근했어야 했다. 각 상태 별로 3가지 상태값 존재 !!!
java 코드
import java.io.*;
import java.util.*;
public class Main {
static int n;
static long[][] dp,data;
static int red = 0, green = 1, blue = 2;
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
public static void main(String[] args) throws IOException {
n = Integer.parseInt(br.readLine());
// ! 집이 n개
dp = new long[1001][3]; // ! 각 집은 0,1,2 r,g,b의 값을 가질 수 있음
for (int i = 1; i <= n; i++) {
Arrays.fill(dp[i], 1000000);
}
// ! 각 집은 빨강, 초록, 파랑 중 하나의 색. 각각의 비용 주어졌을 때 모든 집 칠하는 비용의 최솟값
// ! 이전 집과 색이 같지 않아야 함.
data = new long[n+1][3];
for (int i = 1; i <= n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
int value = Integer.parseInt(st.nextToken());
data[i][j] = value;
}
}
dp[1][red] = data[1][red];
dp[1][green] = data[1][green];
dp[1][blue] = data[1][blue];
for (int i = 2; i <= n; i++) {
dp[i][red] = Math.min(dp[i - 1][green], dp[i - 1][blue]) + data[i][red];
dp[i][green] = Math.min(dp[i - 1][red], dp[i - 1][blue]) + data[i][green];
dp[i][blue] = Math.min(dp[i - 1][red], dp[i - 1][green]) + data[i][blue];
}
long res = 1000000;
res = Math.min(Math.min(dp[n][red], dp[n][green]), dp[n][blue]);
System.out.println(res);
}
}