[Java] 백준(실버-1) 1149번 - RGB거리
문제 풀이
이번 문제는 동적 계획법 DP를 이용해 점화식을 세운다면 쉽게 풀 수 있는 문제이다.
아이디어 도출
처음엔 문제를 잘 이해하기 어려울 수 있다. 하나씩 살펴보며 간단히 정리해보자.
일단 1번부터 N번까지의 집을 색칠해야하는데 이때, 색칠할 수 있는 색의 종류는 빨강, 초록, 파랑 3가지가 주어진다. 그리고 각 집마다 색을 칠하는 비용이 주어진다. 우리는 N번까지의 모든 집을 칠할 때의 최소가 되는 비용을 구해야 한다.
일단 여기까지만 생각해보면, 각 집마다 R,G,B의 비용 중 가장 싼 색을 선택하면 될 것 같은데, 문제의 요구사항을 보면 근접한 집끼리는 같은 색으로 칠하면 안된다는 점을 고려해야 한다.
예를 들어 3번 집에 초록색을 칠한다면, 2번집과 4번집은 초록색을 칠할 수 없다. 이러한 조건으로 인해 최소 비용을 구할 때 그냥 최솟 비용만을 구한다면 오답이 된다.
1
2
3
4
3
1 100 103
1 103 200
100 1 103
위와 같은 예시가 있다고 가정한다면, 1(R) + 103(G) + 100(R) = 204로 조건을 잘 지키며 색을 칠할 수 있다. 하지만 이 비용이 과연 최소비용이 맞을까? 아니다. 100(G) + 1(R) + 1(G) = 102가 정답이 된다. 여기서 볼 수 있듯이 그냥 단순히 최소가 돠는 비용을 찾아 누적합을 구하면 안된다는 것을 알 수 있다.
결과적으로 집마다 최소비용을 구해 누적합을 구하는 것이 아니라, 모든 집을 칠하는 경우의 수를 찾아서 최종적으로 최소가 되는 누적합을 찾아야 한다.
DP 점화식
이때, 동적계획법을 어떻게 이용할 수 있을까? R, G, B에 따른 3가지 케이스 별로 비용을 담은 배열과 누적합을 담은 DP 테이블을 이용하면 된다.
DP 테이블을 갱신하기 위한 점화식은 다음과 같다.
- Red일 경우:
Cost[N][0] = min( Cost[N-1][1], Cost[N-1][2] ) + Cost[N][0] - Green일 경우:
Cost[N][1] = min( Cost[N-1][0], Cost[N-1][2] ) + Cost[N][1] - Blue일 경우:
Cost[N][2] = min( Cost[N-1][0], Cost[N-1][1] ) + Cost[N][2]
위와 같은 점화식을 세우고 이를 재귀함수로 구성하여 메모이제이션을 적용해 해당 배열을 아직 탐색하지 않았다면 재귀를 해주고, 그 외의 경우는 DP배열의 값을 반환해주면 된다.
문제 풀이를 위해 작성한 코드는 아래와 같다.
작성코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.io.*;
import java.util.*;
class Main {
// DP 테이블 선언
static int[][] D;
// 색상별 비용을 담을 배열
static int[][] arr;
public static void main(String[] args) throws IOException {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
// 1번 규칙: 1번 집과 2번 집의 색은 달라야 한다.
// 2번 규칙: N-1번 집과 N번 집의 색은 달라야 한다.
// 3번 규칙: i번 집은 i-1번 집, i+1번 집의 색과 달라야 한다.
// 모든 집을 탐색하며 경로마다 경우의 수를 찾아 가장 작은 누적합을 찾아야 한다.
// 1번집을 DP 테이블의 0번째로 초기화
int N = Integer.parseInt(br.readLine());
// 안쪽 배열은 R,G,B 3가지이기에 3의 크기로 초기화
D = new int[N][3];
arr = new int[N][3];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
arr[i][0] = Integer.parseInt(st.nextToken());
arr[i][1] = Integer.parseInt(st.nextToken());
arr[i][2] = Integer.parseInt(st.nextToken());
}
// DP 테이블의 1번 집의 R,G,B 비용 설정
D[0][0] = arr[0][0];
D[0][1] = arr[0][1];
D[0][2] = arr[0][2];
int result = Math.min(recursion(N-1, 0), Math.min(recursion(N-1, 1), recursion(N-1, 2)));
bw.write(result+"\n");
}
}
/**
* DP 테이블을 갱신할 재귀함수
*
* 점화식은 아래와 같다.
* Red: arr[N][0] = min(arr[N-1][1], arr[N-1][2]) + arr[N][0]
* Green: arr[N][1] = min(arr[N-1][0], arr[N-1][2]) + arr[N][1]
* Blue: arr[N][2] = min(arr[N-1][0], arr[N-1][1]) + arr[N][2]
*/
public static int recursion(int N, int color) {
/**
* 탐색하지 않은 집의 위치라면 R,G,B 중 최소 비용을 갱신한다.
* Red일 경우 == 0
* Green일 경우 == 1
* Blue일 경우 == 2
*/
if(D[N][color] == 0) {
if(color == 0) {
D[N][0] = Math.min(recursion(N-1, 1), recursion(N-1, 2)) + arr[N][0];
}
else if(color == 1) {
D[N][1] = Math.min(recursion(N-1, 0), recursion(N-1, 2)) + arr[N][1];
}
else {
D[N][2] = Math.min(recursion(N-1, 0), recursion(N-1, 1)) + arr[N][2];
}
}
// 메모이제이션을 통해 탐색한 집이라면 위 제어문을 타지 않고 바로 반환한다.
return D[N][color];
}
}
출처
- 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.