문제
풀이
다이나믹 프로그래밍을 사용한다.
- N번 집을 칠할 때, 1번 집의 색의 영향을 받는다.
- 1번 집을 R로 칠한 경우, G로 칠한 경우, B로 칠한 경우 세 가지를 모두 검사해야 한다.
- 1번 집을 칠한 색이외의 cache에는 충분히 큰 값을 두어 2번 집을 칠할 때 선택되지 않도록 해야한다.
- i번 집을 j색으로 칠했을 때의 최솟값은 i번 집을 j색으로 칠한 비용과 i - 1번 집을 j 이외의 색으로 칠한 비용의 합의 최솟값이다.
- N번 집은 1번 집을 칠했을 때의 색으론 칠할 수 없으니 그 경우는 제외해야 한다.
코드
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int house[1001][3];
int cache[1001][3];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(nullptr);
int N;
cin >> N;
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < 3; ++j)
{
cin >> house[i][j];
}
}
// 첫번째 집에서 R을 선택했을 때, G를 선택했을 때, B를 선택했을 때
// 3가지 경우를 비교한다.
int color = 0;
int answer = INT_MAX;
while (color < 3)
{
// 선택한 색 외에는 충분히 큰 값으로 설정
cache[0][color] = house[0][color];
cache[0][(color + 1) % 3] = 10000;
cache[0][(color + 2) % 3] = 10000;
// 이전 집들 중 자신의 색과 다른 색의 경우만 비교한다.
for (int i = 1; i < N; ++i)
{
cache[i][0] = min(house[i][0] + cache[i - 1][1], house[i][0] + cache[i - 1][2]);
cache[i][1] = min(house[i][1] + cache[i - 1][0], house[i][1] + cache[i - 1][2]);
cache[i][2] = min(house[i][2] + cache[i - 1][0], house[i][2] + cache[i - 1][1]);
}
for (int i = 0; i < 3; ++i)
{
// 마지막 집과 첫번째 집이 동일한 색인 경우는 제외한다.
if (i == color)
{
continue;
}
answer = min(answer, cache[N - 1][i]);
}
// 다음 색으로 넘어간다.
color++;
}
cout << answer;
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 1005: ACM Craft (0) | 2023.10.17 |
---|---|
[백준][C++] 20040: 사이클 게임 (0) | 2023.10.16 |
[백준][C++] 10942: 팰린드롬? (0) | 2023.10.14 |
[백준][C++] 9252: LCS 2 (0) | 2023.10.14 |
[백준][C++] 2239: 스도쿠 (0) | 2023.10.12 |