https://www.acmicpc.net/problem/1149
문제
> RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
> 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다.
> 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때,
아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
1. 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
2. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
3. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.접근
DP를 사용해 집의 수가 적을 때 최소의 비용으로 칠하는 규칙을 구하고 집이 많아졌을 때를 이를 통해 구해낸다.
위 규칙을 보면 1번 2번은 다른 색이어야 한다, N번과 N-1은 다른색이어야 한다, i번은 i-1, i+1과 다른 색이어야 한다로 유추 할 수 있는 규칙은 i-1과 i+1이 다른색이어야 한다라는 얘기가 없으니 결국 i와 i-1만 다르게 칠해주면 된다는 뜻이다.
수식으로 쓰면 이렇게 된다.
문제해결
> 집의 번호와 칠할 색 두개를 받아야하므로 이차원 벡터형태로 dp와 집의 색비용 RGB를 선언한다.
> 1부터 N번째 집까지 각각의 색별로 비용을 RGB 벡터에 입력을 받는다.
> 앞서 도출한 수식을 사용할 건데 일단 첫 집에 대해서 각 비용을 dp[1]에대해 RGB 순서로 0,1,2번 인덱스에 각 비용을 넣는다.
> 2번째 집부터 반복문을 사용해 3가지 색에대해 최소비용을 각각 구한다. 수식을 사용해 j에서 색을 고르면 dp[i-1]에 대해 (j+1) % 3번째 색과 (j+2) % 3번째 색중 최소값을 선택하고 j색의 비용을 더해준다.
> j가 0번색이면 0+1 % 3해서 1번색, 0+2 % 3해서 2번색 이런식으로 색이 들어간다.
> N번째 집에대해서 구해준 뒤, 해당 N번 째를 어떤 색으로 칠했을 때 최소 비용이 나오는지 구하기 위해 각 색중 min을 구해 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<vector<int>> RGB(N+1, vector<int>(3));
vector<vector<int>> dp(N + 1, vector<int>(3));
for (int i = 1; i <= N; i++)
{
for (int j = 0; j < 3; j++)
{
cin >> RGB[i][j];
}
}
dp[1][0] = RGB[1][0];
dp[1][1] = RGB[1][1];
dp[1][2] = RGB[1][2];
for (int i = 2; i <= N; i++)
{
for (int j = 0; j < 3; j++)
{
dp[i][j] = min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3]) + RGB[i][j];
}
}
cout << min({ dp[N][0], dp[N][1], dp[N][2]}) << '\n';
}
후기
규칙을 수식화하는데 좀 헤맸지만 계속 읽어보니 단순한 규칙이어서 i와 i-1번만 비교하면 되는 규칙이었다.
이차원 벡터로 dp를 다루는건 처음이라 복잡했지만 할만했다.
