문제
풀이
DP를 사용해서 풀 수 있습니다.
메모이제이션을 수행 할 2차원 배열을 만들어줍니다. 3가지 색이 있기 때문에 배열 크기는 N행 3열이 됩니다.
이 문제에서 중요한 점은 앞 뒤로 색이 연속되면 안됩니다. 그렇기 때문에 다음의 코드와 같이 현재 color가 rgb중 r이라고 하면 앞 집은 g와 b중 하나가 되어야 합니다.
1
2
3
// r:0, g:1, b:2
// 현재집 i를 0(빨강)으로 칠하므로 앞집 i-1은 1(초록)과 2(파랑)로 칠합니다.
cache[i][0] = min(cache[i-1][1], cache[i-1][2]) + cost[i][0];
반복문을 사용한 코드와 재귀함수를 사용한 코드 두 가지를 작성해봤습니다.
반복문 사용
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
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
// 집의 가격을 저장하는 vector
vector<vector<int>> cost(n, vector<int>(3));
for (int i = 0; i < n; i++)
for (int j = 0; j < 3; j++)
cin >> cost[i][j];
// 최대가격을 저장하는 벡터
vector<vector<int>> cache(n, vector<int>(3, 0));
// 가장 앞집의 최대 가격은 자신의 가격
for (int i = 0; i < 3; i++)
cache[0][i] = cost[0][i];
// 메모이제이션
for (int i = 1; i < n; i++)
{
cache[i][0] = min(cache[i - 1][1], cache[i - 1][2]) + cost[i][0];
cache[i][1] = min(cache[i - 1][0], cache[i - 1][2]) + cost[i][1];
cache[i][2] = min(cache[i - 1][1], cache[i - 1][0]) + cost[i][2];
}
cout << min({cache[n - 1][0], cache[n - 1][1], cache[n - 1][2]});
return 0;
}
재귀함수 사용
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
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n;
int colors[1001][3];
int cache[1001][3];
int getCost(int house, int color)
{
// 기저사례
if (house == 0)
return colors[house][color];
// 값을 구한 적 있으면 바로 return
if (cache[house][color] != -1)
return cache[house][color];
if (color == 0)
return cache[house][0] = colors[house][0] + min(getCost(house - 1, 1), getCost(house - 1, 2));
else if (color == 1)
return cache[house][1] = colors[house][1] + min(getCost(house - 1, 0), getCost(house - 1, 2));
else
return cache[house][2] = colors[house][2] + min(getCost(house - 1, 1), getCost(house - 1, 0));
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> colors[i][0] >> colors[i][1] >> colors[i][2];
memset(cache, -1, sizeof(cache));
int cand0 = getCost(n, 0);
int cand1 = getCost(n, 1);
int cand2 = getCost(n, 2);
cout << min(min(cand0, cand1), cand2);
return 0;
}
