-개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.
문제 설명
난이도: 실버 1
사용 언어: JAVA
N개의 집이 일렬로 쭉 세워져 있는 RGB거리가 있습니다. 각각의 집을 빨강, 초록, 파란색 중 하나를 선택해서 칠해야 하며, 각각의 색깔로 칠하는데 드는 비용은 모두 다르며, 비용은 입력으로 주어집니다.
그리고 규칙이 하나 존재하는데, 바로 모든 집은 앞, 그리고 뒤의 집과 색깔이 같으면 안 된다는 것입니다. 가장 앞에 있는 첫 번째 집은 두 번째 집과 색이 같으면 안 되고, 네 번째 집은 세 번째, 그리고 다섯 번째 집과는 색깔이 같으면 안 됩니다. 즉 연속된 집을 같은 색깔로 두 번 이상 칠할 수 없습니다.
이때, 마지막 집까지 색을 칠했을 때 드는 최소 비용을 구하는 문제입니다.
풀이
이 문제는 다이나믹 프로그래밍을 이용해 해결할 수 있습니다. 저는 arr와 cost라는 두 개의 이차원 배열을 이용했습니다. arr배열은 입력 값을 저장시켜두는 용도로, 그리고 cost 배열은 다이나믹 프로그래밍을 위한 결괏값을 저장하는 용도로 사용했습니다.
백준에서 제시한 예제를 가지고 설명을 해보겠습니다.
3
26 40 83
49 60 57
13 89 99
첫 번째 집은 빨강으로 칠할 때는 26, 초록으로 칠할 때는 40, 파랑으로 칠할 때는 83의 비용이 든다는 것을 의미합니다. 두 번째, 세 번째 집도 같은 맥락으로 이해할 수 있습니다. 여기서 당연히 첫 번째 집만 색칠을 하는 경우에는 누적된 비용도 26 40 83일 것입니다. 이 값들을 cost 배열에 추가시켜 줍니다.
두 번째 집을 칠 할 때는, 첫 번째 집의 색을 고려해야 합니다. 즉, 두 번째 집을 빨강으로 칠하려면, 첫 번째 집은 초록, 또는 파랑으로 칠했어야 하고, 파랑으로 칠하려면, 첫 번째 집이 빨강 혹은 초록으로 칠해졌어야 합니다.
위의 그림은 cost 배열 내에서 배열을 채워나가는 과정의 일부입니다. cost 배열의 첫 칸은 빨강, 두 번째 칸은 초록, 세 번째 칸은 파랑을 의미합니다. 이때 두 번째 집을 빨간색으로 칠 할 때의 누적 비용은, 첫 번째 집이 초록을 칠했을 때의 누적 비용에 두 번째 집이 빨강으로 칠할 때의 비용을 더한 값과 첫 번째 집이 파랑을 칠했을 때의 누적 비용에 두 번째 집이 빨강으로 칠할 때의 비용을 더한 값 중 더 작은 것으로 채워넣습니다. 당연히 89가 132보다 작기 때문에 cost 배열의 첫 번째 칸에는 89가 들어가게 됩니다.
cost에 들어가는 각 값들은, 해당 집에서 이 색깔을 선택했을 때 가질 수 있는 지금까지의 누적 비용의 최솟값을 뜻한다고 생각하시면 됩니다. 이런 식으로 N번 째 집까지의 누적 비용을 색깔 별로 구해줍니다. 그리고 cost 배열의 N 번째 값들 중 가장 작은 값을 최종적으로 출력해주면 됩니다.
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
|
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N;
N = Integer.parseInt(br.readLine());
int i, j;
int[][] arr = new int[N][3];
int[][] cost = new int[N][3];
String s;
StringTokenizer st;
for (i = 0; i < N; i++) { // arr 배열에 입력 값 저장
s = br.readLine();
st = new StringTokenizer(s);
for (j = 0; j < 3; j++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for (j = 0; j < 3; j++) { // cost[0]은 arr[0]과 동일
cost[0][j] = arr[0][j];
}
for (i = 1; i < N; i++) { // cost[0]은 이미 채워넣었으니 1부터 N까지 반복하며
if (cost[i - 1][1] < cost[i - 1][2]) // 빨강을 위한 cost[i][0]에 둘 중에 더 작은 쪽을 넣는데,
cost[i][0] = cost[i - 1][1] + arr[i][0]; // cost[i-1][1]은 윗 집이 초록을 골랐을 때의 누적 비용이고,
else
cost[i][0] = cost[i - 1][2] + arr[i][0]; // cost[i-1][2]는 윗 집이 파랑을 골랐을 때의 누적 비용.
if (cost[i - 1][0] < cost[i - 1][2])
cost[i][1] = cost[i - 1][0] + arr[i][1];
else
cost[i][1] = cost[i - 1][2] + arr[i][1];
if (cost[i - 1][0] < cost[i - 1][1])
cost[i][2] = cost[i - 1][0] + arr[i][2];
else
cost[i][2] = cost[i - 1][1] + arr[i][2];
}
Arrays.sort(cost[N - 1]); // 정렬을 해서, 가장 작은 값을 출력
System.out.println(cost[N - 1][0]);
}
}
|
cs |
'백준 온라인 저지 > Silver' 카테고리의 다른 글
[BOJ] 1590 - 캠프가는 영식 (0) | 2021.02.07 |
---|---|
[BOJ] 1303 - 전쟁 - 전투 (1) | 2021.02.06 |
[BOJ] 2178 - 미로 탐색 (0) | 2021.02.05 |
[BOJ] 1743 - 음식물 피하기 (0) | 2021.02.04 |
[BOJ] 11726 - 2xn 타일링 (0) | 2021.02.04 |