17404번: RGB거리 2
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
1149번: RGB거리
첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나
www.acmicpc.net
위의 문제에서 1번 집과 N번 집도 이웃이라는 조건이 추가되었습니다.
저는 1번 집에 칠할 색을 고정시켜놓고 모든 집을 칠하는 비용의 최솟값을 구하였습니다.
색이 3가지이므로 최솟값은 3번 구하게 되며, 1번 집이 빨강일 경우, 초록일 경우, 파랑일 경우를 따로 구해줍니다.
solve함수는 위의 문제와 동일하게 돌아갑니다.
1번 집이 빨강일 경우에는 N번 집이 초록, 파랑을 골랐을 때의 최솟값
1번 집이 초록일 경우에는 N번 집이 빨강, 파랑을 골랐을 때의 최솟값
1번 집이 파랑일 경우에는 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
53
54
55
56
57
58
59
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int list[][], dp[][];
static int N, ans;
static void solve() {
for (int i = 2; i <= N; i++) {
dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + list[i][0];
dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + list[i][1];
dp[i][2] = Math.min(dp[i - 1][0], dp[i - 1][1]) + list[i][2];
}
}
static void func() {
dp[1][0] = list[1][0];
dp[1][1] = 1001;
dp[1][2] = 1001;
solve();
ans = Math.min(dp[N][1], dp[N][2]);
dp[1][0] = 1001;
dp[1][1] = list[1][1];
dp[1][2] = 1001;
solve();
ans = Math.min(ans, Math.min(dp[N][0], dp[N][2]));
dp[1][0] = 1001;
dp[1][1] = 1001;
dp[1][2] = list[1][2];
solve();
ans = Math.min(ans, Math.min(dp[N][0], dp[N][1]));
System.out.println(ans);
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
list = new int[N + 1][3];
dp = new int[N + 1][3];
for (int i = 1; i <= N; i++) {
st = new StringTokenizer(br.readLine());
list[i][0] = Integer.parseInt(st.nextToken());
list[i][1] = Integer.parseInt(st.nextToken());
list[i][2] = Integer.parseInt(st.nextToken());
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 9177 단어 섞기 (0) | 2021.03.19 |
|---|---|
| boj 10942 팰린드롬? (0) | 2021.03.12 |
| boj 2616 소형기관차 (0) | 2021.02.27 |
| boj 11049 행렬 곱셈 순서 (0) | 2021.02.20 |
| boj 1915 가장 큰 정사각형 (0) | 2021.02.20 |