1149 RGB거리
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 (추가 시간 없음) | 128 MB | 76545 | 38994 | 29100 | 50.546% |
문제
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 99
예제 출력 1
96
예제 입력 2
3
1 100 100
100 1 100
100 100 1
예제 출력 2
3
예제 입력 3
3
1 100 100
100 100 100
1 100 100
예제 출력 3
102
예제 입력 4
6
30 19 5
64 77 64
15 19 97
4 71 57
90 86 84
93 32 91
예제 출력 4
208
예제 입력 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 19
예제 출력 5
253
코드
import java.io.*;
import java.util.Arrays;
import java.util.Collections;
public class P_1149 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[][] rgb = new int[n + 1][3];
int[][] dp = new int[n + 1][3];
for (int i = 1; i<= n; i++) rgb[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int i = 0; i < 3; i++) dp[1][i] = rgb[1][i];
for (int i = 2; i<= n; i++) {
dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + rgb[i][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + rgb[i][1];
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + rgb[i][2];
}
bw.write(Integer.toString(Arrays.stream(dp[n]).min().getAsInt()));
bw.flush();
}
}코드 설명
dp[n]은 n번 집까지 칠하는 비용의 최솟값을 의미한다.
그런데 이 문제의 경우 n - 1번 집이 어떤 색으로 칠해져있는지 저장을 해야 한다.
그래서 dp를 이차원 배열로 선언했다.
dp[n][0] = n번 집을 빨강으로 칠할 때 비용의 최솟값
dp[n][1] = n번 집을 초록으로 칠할 때 비용의 최솟값
dp[n][2] = n번 집을 파랑으로 칠할 때 비용의 최솟값
n번째 집을 칠하기 위해서는 n-1번 집이 초록 혹은 파랑으로 칠해져야 하는데 이 때 n-1번 집을 초록, 파랑으로 칠한 경우 중 최솟값을 이용해야한다.
그래서 dp[n][0] = min(dp[n - 1][1], dp[n - 1][2]) + rgb[n][0]이 된다.
이 때, rgb[n][0]은 n번째 집을 빨강으로 칠하는 비용이다.
n번째 집을 초록 혹은 파랑으로 칠할 때도 마찬가지이다.
초록으로 칠할 때는 n-1집이 빨강, 파랑 중 하나로 칠해져있어야하며 이 값중 최소 비용을 골라야 한다.
파랑으로 칠할 때는 n-1집이 빨강, 초록 중 하나로 칠해져있어야하며 이 값중 최소 비용을 골라야 한다.
즉, 점화식은 다음과 같다.
dp[n][0], dp[n][1], dp[n][2] 중 최솟값이 정답이 된다.
