[Silver I] RGB거리 - 1149
성능 요약
메모리: 14536 KB, 시간: 124 ms
분류
다이나믹 프로그래밍
제출 일자
2025년 4월 8일 11:34:54
문제 설명
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보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
구하고자 하는 것
모든 집을 칠하는 비용이 최소가 되도록 하여 이 값을 구해야 한다.
풀이 설계하기
최소값을 계속 취하되, 전의 집과 후의 집과 색깔이 달라야 한다.
그래서 집이 N개면 3^N 만큼의 탐색 가짓수가 발생한다.
그리고 N이 1000이므로, 백트래킹으로 풀 수는 없다.
보편적인 원칙에 따라 1초가 대략 10억번 정도의 연산이라 가정하고 접근한다면, N^3 정도가 마지노선일 것이다.
매 순간마다 최소값을 취하는 그리디와, 이전 값의 상태를 활용하는 DP 정도가 떠오른다.
그런데 각각의 집마다 칠하는 비용이 다르므로, 전 집에서 최대한 싼 것을 고르더라도 다음 집에서 이전 집에서 사용된 색을 피하다가 아주 큰 비용을 선택해야 하는 경우도 있을 수 있다.
따라서 이전의 상태를 활용하는 DP로 풀 수 있다.
(사실 DP도장인 시점에서 의미는 없으나, 코딩 테스트 시험에서는 유형을 알려주지도 않는다.)
(심지어 2차원 공간에서 출제되어 BFS/DFS로 유혹하는 경우도 많다.)
점화식 세우기
여전히 다차원 배열을 활용하는 유형이라는 감을 잡지 못했다.
우선 dp[i]가 [i]번 집까지 최선의 값이라고 가정한다면, 위에 그리디 부분에서 언급한 문제에 빠지게 된다.
그러면 이차원 배열로 나타내면 더 많은 것을 표현할 수 있지 않을까?
이 문제의 주요 제약 조건은 이전 집에서 사용한 색을 다음 집에서 칠할 수 없다는 것이다.
i번 집의 색은 i-1번, i+1번 집과 달라야 한다.
색은 R, G, B가 있으므로(0, 1, 2번 색으로 나타낸다) 다음과 같은 사실을 도출 가능하다.
- i번 집의 색이 R이면 i-1, i+1번 집은 (G, B) 중 하나이다.
- i번 집의 색이 G이면 i-1, i+1번 집은 (R, B) 중 하나이다.
- i번 집의 색이 B이면 i-1, i+1번 집은 (R, G) 중 하나이다.
이러한 사실로 나타낸다면 현재 집은 이전 집의 두 가짓수에서 비용이 작은 집 + 현재 집 비용으로 나타낼 수 있지 않을까?
그리고 이전 집의 가짓수는 한정되어 있다.
위의 세 사실을 식으로 나타내면
- i번 집의 색이 R이면, i번째 집의 R 색칠 비용 + i-1번 집까지 칠하는 비용 중 최소
- i번 집의 색이 G이면, i번째 집의 G 색칠 비용 + i-1번 집까지 칠하는 비용 중 최소
- i번 집의 색이 B이면, i번째 집의 B 색칠 비용 + i-1번 집까지 칠하는 비용 중 최소
그리고 i-1번까지 칠하는 비용 중 최소는 다시 위의 점화식을 타고 올라가 처음 집까지 거슬러 올라간다.
그러면 처음 집에서 R, G, B 중 한 가지 색을 칠했을 것이다.
두 번째 집에서는 각각 (G, B) 중 하나, (R, B) 중 하나, (R, G)중 하나를 칠할 수 있다.
바꾸어 말하면 두 번째 집에서 R, G, B 중 한 가지 색을 칠했다면, 첫 번째 집에서는 (G, B) 중 하나, (R, B) 중 하나, (R, G)중 하나를 칠했다는 뜻이다.
이제 최종 점화식 윤곽이 슬슬 드러난다.
- i번 집의 색이 R이면, i번째 집의 R 색칠 비용 + i-1번 집을(G, B)중 하나 칠한 최소값
-> dp[i]에서 R칠함 + min(dp[i-1]에서 G 칠하는 경우와 이전까지 최소, dp[i-1]에서 B 칠하는 경우와 이전까지 최소) - i번 집의 색이 G이면, i번째 집의 R 색칠 비용 + i-1번 집을(R, B)중 하나 칠한 최소값
-> dp[i]에서 G칠함 + min(dp[i-1]에서 R 칠하는 경우와 이전까지 최소, dp[i-1]에서 B 칠하는 경우와 이전까지 최소) - i번 집의 색이 B이면, i번째 집의 R 색칠 비용 + i-1번 집을(R, G)중 하나 칠한 최소값
-> dp[i]에서 B칠함 + min(dp[i-1]에서 R 칠하는 경우와 이전까지 최소, dp[i-1]에서 G 칠하는 경우와 이전까지 최소)
이차원 배열을 도입하면, i번 집에서 j번 색을 칠한 지금까지 최소 비용을 표현할 수 있다
dp[i][j] = i번 집에서 j번 색을 칠한 i번까지의 최소 비용
(0 <= i < N, 0 <= j < 3)
이제 0번을 초기화한 다음 반복문을 통해(i, j의 조건은 위와 같다)
for(int i = 0; i < N; i++) {
dp[i][0] = cost[i][0] + Math.min(dp[i-1][1], dp[i][2])
dp[i][1] = cost[i][1] + Math.min(dp[i-1][0], dp[i][2])
dp[i][2] = cost[i][2] + Math.min(dp[i-1][0], dp[i][1])
}시간 복잡도
매 i마다 3번의 연산이 일어나며, dp[0]의 초기화 포함 N번의 연산이 일어난다.
따라서 O(3 * N) = O(N)이므로 상당히 널널하게 해결 가능하다.
풀이
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int N = Integer.parseInt(br.readLine());
int[][] costs = new int[N][3];
int[][] dp = new int[N][3];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
costs[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < 3; i++) {
dp[0][i] = costs[0][i];
}
for (int i = 1; i < N; i++) {
dp[i][0] = costs[i][0] + Math.min(dp[i-1][1], dp[i-1][2]);
dp[i][1] = costs[i][1] + Math.min(dp[i-1][0], dp[i-1][2]);
dp[i][2] = costs[i][2] + Math.min(dp[i-1][0], dp[i-1][1]);
}
int answer = Integer.MAX_VALUE;
for (int i = 0; i < 3; i++) {
answer = Math.min(answer, dp[N-1][i]);
}
System.out.println(answer);
}
}문제를 많이 푸는 것도 좋으나, 점화식 세울 수 있는 역량 향상이 핵심이기에 풀이를 상세히 적어 두려 한다.
