1149번 : RGB 거리
문제)
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
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
|
// 1149. RGB 거리
#include <iostream>
#include <vector>
using namespace std;
int n;
vector<vector<int>> vec;
vector<vector<int>> dp;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
vec.resize(n, vector<int>());
dp.resize(n + 1, vector<int>(n + 1, 100000));
int a;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < 3; j++)
{
cin >> a;
vec[i].push_back(a);
}
}
for (int i = 0; i < 3; i++)
{
dp[n][i] = 0;
}
int ans = 100000;
for (int i = n - 1; i >= 0; i--)
{
for (int j = n - 1; j >= 0; j--)
{
for (int k = 0; k < 3; k++)
{
if (i > 0 && j == k) continue;
dp[i][j] = min(dp[i][j], dp[i + 1][k] + vec[i][k]);
}
}
}
for (int i = 0; i < 3; i++)
{
ans = min(ans, dp[0][i]);
}
cout << ans;
return 0;
}
|
cs |
출처 : https://www.acmicpc.net/problem/1149
'Develop > 백준 (Cpp)' 카테고리의 다른 글
[백준] 2776번 : 암기왕 (C++) (0) | 2023.09.16 |
---|---|
[백준] 11053번 : 가장 긴 증가하는 부분 수열 (C++) (0) | 2023.09.16 |
[백준] 2565번 : 전깃줄 (C++) (0) | 2023.09.16 |
[백준] 11054번 : 가장 긴 바이토닉 부분 수열 (C++) (0) | 2023.09.16 |
[백준] 6497번 : 전력난 (C++) (0) | 2023.09.15 |