백준 5577번 RBY팡! (c++)

주어지는 초기상태가 4개이상 연속된 공이 없다는 조건이 중요하다

 

최대 10000개의 공을 전부 3가지 색으로 바꿔가며 테스트하면 시간초과가 나지만,

어짜피 위나 아래의 공과 색깔이 같은 경우에만 바뀌는 의미가 있기 때문에 2*n^2 의  경우만 탐색해주면된다

솔직히 지나치게 널널한거 아닌가 싶기도 하고..

 

signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		ball.push_back(a);
	}
	
	for (int i = 0; i < n; i++)
	{
		if (ans == 0) break;
		int tmp = ball[i];
		if (i != 0)
		{
			ball[i] = ball[i - 1];
			ans = min(ans, simulation(ball));
		}
		if (i != n - 1)
		{
			ball[i] = ball[i + 1];
			ans = min(ans, simulation(ball));
		}
		ball[i] = tmp;
	}
	cout << ans << endl;

}

모든 공을 순회하며 위 아래 색으로 바꾼경우를 한번씩 테스트 해 준다. 인덱스 초과 주의

 

int n;
vector<int> ball;
int ans = 210000000;

int simulation(vector<int> &arr)
{
	vector<int> tmp;
	tmp.push_back(arr[0]);

	for (int i = 1; i < n; i++)
	{
		if (tmp.back() != arr[i])
		{
			int idx = tmp.size();
			if (idx >= 4)
			{
				int color = tmp[idx - 1];
				if (tmp[idx-2] == color && tmp[idx-3] == color && tmp[idx-4] == color)
				{
					while (tmp.back() == color)
					{
						tmp.pop_back();
					}
				}
			}
			tmp.push_back(arr[i]);
		}
		else
		{
			tmp.push_back(arr[i]);
		}
	}

	int idx = tmp.size();
	if (idx >= 4)
	{
		int color = tmp[idx - 1];
		if (tmp[idx - 2] == color && tmp[idx - 3] == color && tmp[idx - 4] == color)
		{
			while (tmp.back() == color)
			{
				tmp.pop_back();
				if (tmp.empty()) break;
			}
		}
	}
	return tmp.size();
}

공을 하나씩 쌓으면서 공의 색깔이 연속되지 않을때마다 한번씩 4개이상이 연속된 상태인지 검사해줬다

단순히 생각해서 4개 이상 쌓이면 무조건 pop  시작이므로 인덱스로 접근해 판별해주었다.

pop할때는 제대로 색이 달라질때까지 pop 해주었다.

Queue를 사용하려니 연속을 판별하기위해 공을 뺐다 넣었다 굉장히 번거로워져서 인덱스로 접근이 가능하고 pop도 가능한 vector를 사용하였다.

 

주의할점은 인덱스를 다 돌고 나왔을때, 벡터에 남은 공들이 연속인지도 한번 확인해줘야 한다는것이다.

공 색이 달라졌을때 벡터를 체크하므로 따로 처리해주지 않는다면 틀린다.

 

그리고 벡터의 현재 길이를 반환해주면 된다.

 

 

 

 

골드 3~4정도 되는 문제가 아닌가 싶어 어리둥절한 문제