백준 17404 - RGB거리 2 (C++)
여러 개의 집이 순서대로 놓여 있고, 이 집의 외벽에 색을 칠하고자 한다.
하나의 집에 인접한 두 집과 같은 색이 아니도록 칠하고자 한다.
각 집마다 색을 칠할 때의 비용이 상이하게 책정되어 있다.
인접한 집과 다른 색상이라는 조건을 유지하며 색을 칠할 때 그 비용의 최소를 구하자.
문제 풀이
이 문제는 모든 경우를 탐색하며 그 비용을 구해야 한다.
하지만, 일반적인 완전탐색 방식으로 모든 경우를 탐색하면 말도 안되는 경우의 수가 나온다.
그러므로 다이나믹 프로그래밍을 사용하여 효율적으로 비용의 최소 값을 구해야 한다.
먼저, 첫 번째 집의 색상을 하나로 고정하여 시작하는 DP를 3번 반복하는 것이다.
왜 3번을 할까? 첫 번째 집과 마지막 집의 색이 같으면 안된다는 조건 때문이다.
그렇기 때문에 첫 번째 집을 Red로 칠하는 경우, Green으로 칠하는 경우, Blue로 칠하는 경우를 하나씩 확인해야 한다.
그럼, 이제 DP를 해보자.
먼저, DP는 2차원 배열로 만들 것이다.
DP[i][j] 가 있다면, i는 집의 순번이고 j는 색상이다. (0은 R, 1은 G, 2는 B)
저장될 값은 최소 비용이다.
DP[3][2] 라고 한다면, 3번째 집을 Blue로 칠할 때의 최소 비용이다.
DP[10][1]은 10번째 집을 Green으로 칠할 때의 최소 비용이다.
이렇게 집의 위치와 색상을 함께 고려할 것이다.
이 때, DP[i][0] 은 어떻게 구해야 할까?
i번째 집을 빨간색으로 칠한다고 하면, 일단 i-1번째 집은 빨간색이어선 안된다.
또한, i - 1 개의 집을 칠하는데 들어간 총 비용 + i번째 집을 빨간색으로 칠하는 비용이다.
i - 1 개의 집을 칠하는데 들어가는 총 비용은 i - 1 번째 집이 파란색이냐, 초록색이냐에 따라 다를 수 있다.
그러므로, DP[i][0] 은 std::min(DP[i - 1][1] + Cost[i][j], DP[i - 1][2] + Cost[i][j]) 가 될 것이다.
DP[i][0]에 저장할 값은 최소비용이므로, 이전의 집이 파란색일 때의 총 비용과 초록색일 때의 총 비용중 최소 값을 기준으로 현재 집을 칠하는 비용을 더해서 총 비용의 최소값을 갱신하는 것이다.
이렇게 마지막 집까지 모두 갱신했다고 해보자.
그러면, 마지막 집이 R인 경우의 총 비용, G인 경우의 총 비용, B인 경우의 총 비용 이렇게 3개의 값을 구할 수 있다.
이 3개의 비용 중 가장 작은 비용이 첫 번째 집을 R로 칠하는 경우 중 최소 비용인 것이다.
하지만, 마지막 집은 첫 번째 집과 같은 색일 수 없다는 조건이 있으므로, 마지막 집이 R인 경우의 총 비용은 제외하고, 마지막 집이 G인 경우의 총 비용과 B인 경우의 총 비용만 고려하여 최소를 구하면 된다.
첫 번째 집을 R로 칠할 때의 최소 비용, G로 칠할 때의 최소 비용, B로 칠할 때의 최소비용 총 3개를 구한 뒤 셋 중 최소비용을 구하면 그 값이 답이 된다.
풀이 코드
#define BIGNUMBER 999999999먼저, 최소값을 갱신하기 전 초기값을 잡기 위해 충분히 큰 값을 하나 정의해주었다.
int NumOfHouse = 0;
std::cin >> NumOfHouse;
std::vector<std::vector<int>> Cost(NumOfHouse, std::vector<int>(3, 0));
for (int i = 0; i < NumOfHouse; i++)
{
for (int j = 0; j < 3; j++)
{
std::cin >> Cost[i][j];
}
}이후 입력을 받아주었다. 모든 비용을 Cost에 저장해주었다.
Cost[i][j]는 i번째 집을 j색(0 = R, 1 = G, 2 = B)으로 칠하는 비용이다.
int Answer = BIGNUMBER;
std::vector<std::vector<int>> DP(NumOfHouse, std::vector<int>(3, BIGNUMBER));
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < DP.size(); j++)
{
std::fill(DP[j].begin(), DP[j].end(), BIGNUMBER);
}
DP[0][0] = Cost[0][0];
DP[0][1] = Cost[0][1];
DP[0][2] = Cost[0][2];
for (int j = 0; j < 3; j++)
{
if (i == j)
{
continue;
}
DP[1][j] = DP[0][i] + Cost[1][j];
}
for (int j = 2; j < NumOfHouse; j++)
{
DP[j][0] = std::min(DP[j - 1][1] + Cost[j][0], DP[j - 1][2] + Cost[j][0]);
DP[j][1] = std::min(DP[j - 1][0] + Cost[j][1], DP[j - 1][2] + Cost[j][1]);
DP[j][2] = std::min(DP[j - 1][0] + Cost[j][2], DP[j - 1][1] + Cost[j][2]);
}
for (int j = 0; j < 3; j++)
{
if (j == i)
{
continue;
}
Answer = std::min(Answer, DP[NumOfHouse - 1][j]);
}
}먼저,std::fill을 사용하여 DP배열을 초기화해주었다.
하나의 배열을 재활용 할 것이기 때문에 초기화 코드를 넣어주었다.
DP는 위에서 말했듯이, 첫번째 집이 R인 경우, G인 경우, B인 경우 총 3개의 경우를 진행할 것이다.
DP[0][0], DP[0][1], DP[0][2] 는 Cost[0][0], Cost[0][1], Cost[0][2] 로 초기화 해 주었다.
이후 반복문으로 DP[1]도 갱신해주었다.
그리고 이후, DP[2]부터 DP[NumOfHouse]까지 모두 갱신해주었다.
DP[1]만 따로 갱신한 이유는 첫번째 집을 칠하는 색을 하나로 정해두었기 때문에, DP[1]은 첫번째 집이 어떤 색인지 고려하여 값을 계산할 필요가 없기 때문이다. 첫번째 집이 빨간색이라면 그에 맞게 DP[1]을 갱신하였고, 파란색이라면 그에 맞게 갱신한 것이다.
DP배열을 모두 갱신한 뒤에, DP배열의 마지막에 저장된 총 비용 중 최소값을 Answer에 저장해주었다.
이를, 총 3번(첫 번째 집이 R인경우, G인 경우, B인 경우) 실행하였고, 최종적으로 Answer에 저장된 값이 정답이 된다.
std::cout << Answer;
return 0;마지막으로 답을 출력해주면 된다.
코드 전문
#include <iostream>
#include <vector>
#include <algorithm>
void Init()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
}
#define BIGNUMBER 999999999
int main()
{
Init();
int NumOfHouse = 0;
std::cin >> NumOfHouse;
std::vector<std::vector<int>> Cost(NumOfHouse, std::vector<int>(3, 0));
for (int i = 0; i < NumOfHouse; i++)
{
for (int j = 0; j < 3; j++)
{
std::cin >> Cost[i][j];
}
}
int Answer = BIGNUMBER;
std::vector<std::vector<int>> DP(NumOfHouse, std::vector<int>(3, BIGNUMBER));
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < DP.size(); j++)
{
std::fill(DP[j].begin(), DP[j].end(), BIGNUMBER);
}
DP[0][0] = Cost[0][0];
DP[0][1] = Cost[0][1];
DP[0][2] = Cost[0][2];
for (int j = 0; j < 3; j++)
{
if (i == j)
{
continue;
}
DP[1][j] = DP[0][i] + Cost[1][j];
}
for (int j = 2; j < NumOfHouse; j++)
{
DP[j][0] = std::min(DP[j - 1][1] + Cost[j][0], DP[j - 1][2] + Cost[j][0]);
DP[j][1] = std::min(DP[j - 1][0] + Cost[j][1], DP[j - 1][2] + Cost[j][1]);
DP[j][2] = std::min(DP[j - 1][0] + Cost[j][2], DP[j - 1][1] + Cost[j][2]);
}
for (int j = 0; j < 3; j++)
{
if (j == i)
{
continue;
}
Answer = std::min(Answer, DP[NumOfHouse - 1][j]);
}
}
std::cout << Answer;
return 0;
}