BOJ) 1149 RGB거리 <C++>

문제

www.acmicpc.net/problem/1149

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보다 작거나 같은 자연수이다.

 

로직

이번 문제는 이전에 풀었던 DP문제들과 비슷했다. 위의 조건들이 복잡해 보이지만 결국 한 문장으로 줄일 수 있다.

• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.

이유는 결국 N번째 집이 N - 1번째 다르고 N + 1 번째 집이 N번째 집과 다르다면 N번 집은 N - 1번 집과 N + 1번 집이 다를 수밖에 없는 것이다. 

최솟값을 구하는 방법을 그림으로 그려보면 아래와 같다. 

하지만 최솟값을 한 번에 구하는 방법이 없다. 그래서 각 시작점에 따라서 결과를 저장하면서 마지막에 해당 3개의 값을 비교해서 최솟값을 출력해주면 된다고 생각했다. 모든 값을 저장하면 되기 때문에 특별한 알고리즘이 필요하진 않았다. 

 

모든 input 값들을 vector[n][3]에 저장해두었다. 

이번 문제를 해결할 때, 이전의 값들이 필요한 경우가 없다고 생각되어서 새로운 배열을 생성하지 않고 입력을 받은 배열을 그대로 저장 배열로 사용하기로 하였다. 

 

그다음으로 고민을 해 볼 문제는 바로 이전에 어떤 색을 선택하였는지를 어떤 식으로 표현할 것인가이다. 

처음으로 떠올랐던 아이디어는 pivot[3] = {0, 1, 2} 배열을 사용해 이전의 pivot값을 저장하는 것이었다. 하지만 2중 for문을 활용하여 현재 값의 pivot을 알 수 있기 때문에 이전 값을 저장하지 않아도 현재 pivot과 다른 값을 찾으면 되는 것이었다. 

 

위의 로직을 의사코드로 표현해보면 아래와 같다. 

여기서 코드를 줄이기 위한 한 가지 방법을 생각해내었다. 

분기를 통해 j가 0, 1, 2일때를 나누는 것 방법을 사용하지 않았다.

결국 pivot의 선택지는 0, 1, 2 중에 하나이고 자기 자신을 제외한 값이 나오면 되기 때문에 이전 값은

• (pivot + 1) % 3
• (pivot + 2) % 3

라고 할 수 있다. 이제 이 두 값 중에서 최솟값을 구하면 되는 것이다. 

카테고리 

• DP

코드

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<std::vector<int> > cost;
int n;

void output()
{
	std::cout << std::min({cost[n-1][0], cost[n-1][1], cost[n-1][2]});
}

void solution()
{
	for (int i = 1 ; i <  n ; i++)
		for (int j = 0 ; j < 3 ; j++)
			cost[i][j] += std::min(cost[i - 1][(j + 1) % 3], cost[i - 1][(j + 2) % 3]);
}

void input()
{
	std::cin >> n;
	cost.resize(n + 2, std::vector<int>(3, 0));
	for (int i = 0 ; i < n ; i++)
		for (int j = 0 ; j < 3 ; j++)
			std::cin >> cost[i][j];
}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main(void)
{
	preset();
	input();
	solution();
	output();
}