17404 RGB거리 2

https://www.acmicpc.net/problem/17404

17404번: RGB거리 2

RGB거리 2 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

0.5 초 (추가 시간 없음)

128 MB

959

460

384

50.996%

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번, N번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번, 1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

 

 

<풀이>

1. 이 문제는 기존 RGB거리 문제와 다른 조건이 있는데 첫 번째 집이 마지막 N번집과

색이 같으면  안된다는 조건이다.

 

2. 이 말은 원형 큐처럼 이루어져 마지막 집 다음에 다시 첫번째 집이 붙어있는

집이라고 생각하면 된다.

 

3. 따라서 첫번째 집의 색을 미리 정해놓고 (R일때, G일떄 B일때) 각각

그럼  for( 3 번)

{

  for( 두번째 집부터 range N번째 집까지 )

  {

    R로 시작 하는경우, G로 시작하는경우 B로 시작하는 경우의 점화식을 계산해주면됨.

  }

}

 

4. 구해놓고 RGB중

 

R을 칠했을떄는 B와 G중

G를 칠했을경우 R과 B중

B를 칠했을경우 R과 G중                         

가장 최소비용을 찾으면 된다.

 

#include<iostream>
#include<algorithm>
using namespace std;

int arr[1001][4];
int d[1001][4];
int main(void)
{
	int N;
	cin >> N;
	for (int i = 1; i <= N; ++i)
	{
		for(int k = 1; k <= 3;++k)
			cin >> arr[i][k];
	}

	int ans = 1000 * 1000 + 1;
	for (int i = 1; i <=3; ++i)
	{
		for (int j = 1; j <= 3; ++j)
		{
			if (i == j)
				d[1][j] = arr[1][j];
			else
				d[1][j] = 1000 * 1000 + 1;
		}
		

		for (int q = 2; q <= N; ++q)
		{
			d[q][1] = min(d[q - 1][2], d[q - 1][3]) + arr[q][1];
			d[q][2] = min(d[q - 1][1], d[q - 1][3]) + arr[q][2];
			d[q][3] = min(d[q - 1][1], d[q - 1][2]) + arr[q][3];
		}
		
		for (int e = 1; e <= 3; ++e)
		{
			if (e == i) 
				continue;
			ans = min(ans, d[N][e]);
		}
	}
	cout << ans << '\n';
	
	return 0;
}