https://www.acmicpc.net/problem/1149
문제
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보다 작거나 같은 자연수이다.
출력
첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
예제 입력 출력 1 3
26 40 83
49 60 57
13 89 9996 32 3
1 100 100
100 1 100
100 100 13 3 3
1 100 100
100 100 100
1 100 100102 4 6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91208 5 8
71 39 44
32 83 55
51 37 63
89 29 100
83 58 11
65 13 15
47 25 29
60 66 19253
해결 코드
import java.util.Scanner;
public class Main {
//N개 집
//빨, 초, 파 중 하나를 결정
//각각의 비용이 주어져 있는데 최소비용 구하기
//앞 뒤 집과 색이 같으면 안됨
//시도 1: 단순 재귀 -> 시간초과
//시도 2: greedy
//시도 3: dp
static int n;
static int[][] cost;
static int[][] dp;
public static int chooseColor(int idx, int color) {
if(dp[idx][color] == 0) {
if(color == 0) {
dp[idx][color] = Math.min(chooseColor(idx-1, 1), chooseColor(idx-1, 2)) + cost[idx][color];
}
else if(color == 1) {
dp[idx][color] = Math.min(chooseColor(idx-1, 0), chooseColor(idx-1, 2)) + cost[idx][color];
}
else {
dp[idx][color] = Math.min(chooseColor(idx-1, 0), chooseColor(idx-1, 1)) + cost[idx][color];
}
}
return dp[idx][color];
}
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
cost = new int[n][3]; // 0-R / 1-G / 2-B
dp = new int[n][3];
for(int i=0; i<n; i++) {
for(int j=0; j<3; j++) {
cost[i][j] = scanner.nextInt();
}
}
dp[0][0] = cost[0][0];
dp[0][1] = cost[0][1];
dp[0][2] = cost[0][2];
System.out.println(Math.min(Math.min(chooseColor(n-1, 0), chooseColor(n-1, 1)), chooseColor(n-1, 2)));
}
}
동적 계획법(DP, Dynamic Programming) 이용해 문제를 해결했어야 했다. 첫 시도는 DFS 방식의 재귀를 구현해보았다. 그러나 그 방식은 N 크기의 입력개수가 들어왔을 때 2^N 의 시간복잡도를 가진다. 심지어 N의 1000까지 커질 수있다는 것은 시간을 매우 잡아먹을 것이라는 걸 암시한다. 나는 이러한 계산을 하지 않았고 당연하게 시간초과를 경험하였다. 다음 시도로 백트래킹을 이용해 기존의 DFS 재귀를 보완하고자 했다. 그러나 늘어나는 분기를 획기적으로 줄일 방식이 크게 떠오르지 않았다. 그 다음으로는 당연히 안되겠지만(논리단계에서 채택하지 말았어야 하는 알고리즘이다.) Greedy 알고리즘을 구현해봤고 기본 테스트케이스도 성립하지 않는다는 것을 다시금 확인했다.(아무 생각없이 시간까먹기를 한 셈이다.) 사실 조금만 생각해봐도 DP알고리즘은 기하급수적으로 증가하는 재귀의 분기 수를 획기적으로 줄일 수 있는 방법이었다.
로직 분석
1. 입력 처리
• N개의 집과 각 집을 빨강(0), 초록(1), 파랑(2)으로 칠하는 비용을 2차원 배열 cost[N][3]에 저장한다.
• dp[N][3] 배열을 사용하여 각 집을 특정 색으로 칠하는 최소 비용을 저장한다.
2. DP 기반 재귀 (chooseColor)
• chooseColor(idx, color): idx번 집을 color로 칠했을 때의 최소 비용을 구하는 재귀 함수.
• 이미 계산된 dp[idx][color] 값이 있으면 이를 반환하고, 없으면 idx-1의 최솟값을 활용하여 계산한다.
3. 결과 출력
• 마지막 집(N-1)을 빨강, 초록, 파랑 중 하나로 칠했을 때의 최소 비용을 비교하여 출력.
자료구조 분석
1. cost[N][3] (입력)
• cost[i][j]: i번 집을 j색(0=빨강, 1=초록, 2=파랑)으로 칠하는 비용.
2. dp[N][3] (메모이제이션)
• dp[i][j]: i번 집을 j 색으로 칠했을 때의 최소 비용.
• 메모이제이션을 활용하여 같은 부분 문제를 중복 계산하지 않도록 한다.
알고리즘 분석
1. DP 점화식
chooseColor(idx, color)를 구하기 위해 아래와 같은 점화식을 활용한다:
dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[i][2]
즉,
• i번 집을 빨강(0)으로 칠하려면, 이전 집(i-1)을 초록(1)이나 파랑(2) 중 최소 비용을 가진 색으로 칠한 값에 현재 빨강(0) 비용을 더한다.
• 초록(1), 파랑(2)도 같은 방식으로 계산한다.
2. 초기값 설정
• dp[0][0] = cost[0][0]
• dp[0][1] = cost[0][1]
• dp[0][2] = cost[0][2]
즉, 첫 번째 집의 경우 각각의 색을 칠하는 비용이 그대로 초기값이 된다.
3. 재귀 호출 (Top-down 방식)
public static int chooseColor(int idx, int color) {
if (dp[idx][color] == 0) {
if (color == 0) {
dp[idx][color] = Math.min(chooseColor(idx-1, 1), chooseColor(idx-1, 2)) + cost[idx][color];
}
else if (color == 1) {
dp[idx][color] = Math.min(chooseColor(idx-1, 0), chooseColor(idx-1, 2)) + cost[idx][color];
}
else {
dp[idx][color] = Math.min(chooseColor(idx-1, 0), chooseColor(idx-1, 1)) + cost[idx][color];
}
}
return dp[idx][color];
}
이 함수는 탑다운(Top-down) 방식의 DP로, 재귀적으로 idx번째 집을 특정 색으로 칠하는 최소 비용을 계산한다.
4. 최종 결과 계산
System.out.println(
Math.min(Math.min(chooseColor(n-1, 0), chooseColor(n-1, 1)), chooseColor(n-1, 2))
);
마지막 집(N-1)을 빨강(0), 초록(1), 파랑(2) 중 하나로 칠하는 비용 중 최소값을 출력한다.
시간 복잡도 분석
1. 단순 재귀의 경우 (비효율적)
• 각 chooseColor(idx, color) 호출에서 idx-1에 대해 두 번 호출 → 지수 시간 복잡도 O(2^N)
• 하지만 dp(메모이제이션)를 적용했기 때문에 한 번 계산된 값은 다시 계산되지 않는다.
2. DP를 적용한 경우
• dp[i][j]는 총 N×3개의 상태만 저장하면 된다.
• 각 상태는 한 번만 계산되므로 시간 복잡도는 O(N)
• 즉, 최적화된 DP 알고리즘은 선형 시간에 해결 가능하다.
개선 가능성
현재 재귀 기반의 DP(Top-down 방식)이지만, 반복문 기반의 Bottom-up 방식이 더 최적화될 수 있다.
반복문을 활용한 Bottom-up 방식 (추천)
import java.util.Scanner;
public class Main {
public static void main(String args[]) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] cost = new int[n][3];
int[][] dp = new int[n][3];
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
cost[i][j] = scanner.nextInt();
}
}
// 초기값 설정
dp[0][0] = cost[0][0];
dp[0][1] = cost[0][1];
dp[0][2] = cost[0][2];
// Bottom-up 방식으로 DP 테이블 채우기
for (int i = 1; i < n; i++) {
dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + cost[i][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + cost[i][1];
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + cost[i][2];
}
// 최종 최소 비용 출력
System.out.println(Math.min(Math.min(dp[n - 1][0], dp[n - 1][1]), dp[n - 1][2]));
}
}
✅ 이 코드의 장점
• 반복문을 사용해 더 직관적이고 빠르다.
• 재귀 호출로 인한 오버헤드가 없다.
• 시간 복잡도는 동일하게 O(N) , 공간 복잡도는 O(N)
정리
✅ 자료구조
• cost[N][3]: 입력된 색칠 비용 저장.
• dp[N][3]: 특정 집을 특정 색으로 칠할 때의 최소 비용 저장.
✅ 알고리즘
• 재귀 + DP (Top-down 방식)
• dp[i][j] = min(dp[i-1][x], dp[i-1][y]) + cost[i][j]
(x, y는 j가 아닌 두 가지 색)
• 마지막 집의 최소 비용을 비교하여 정답 출력.
✅ 시간 복잡도
• 일반적인 재귀는 O(2^N) → DP로 최적화하여 O(N)
✅ 개선
• 반복문을 사용한 Bottom-up 방식이 더 효율적이며 권장됨.
'Data Structure - Algorithm > Baekjoon' 카테고리의 다른 글
| [백준 #15649] N과 M (1) (0) | 2025.03.02 |
|---|---|
| [백준 #7568] 덩치 (0) | 2025.03.02 |
| [백준 #1436] 영화감독 숌 (0) | 2025.02.28 |
| [백준 #1018] 체스판 다시 칠하기 (0) | 2025.02.27 |
| [백준 #1427] 소트인사이드 (0) | 2025.02.25 |