Boj 25568) 피라미드

문제

백준 25568

설명

이 문제는 두가지를 이해해야한다.

1. 블럭 조합이 2개 뿐이다.
   • 맨 위부터 3개의 순서가 정해지면 이후에는 그 순서만들 따라야한다.
   • 1 번째 줄은 바꿀 수 없으므로 2번째 줄을 바꾼 총 2개의 패턴만 만들 수 있다.
2. 양쪽 모두 필요한 색깔이 들어가는 교환은 우선시 해야한다. (그리디)
   • 예를들어 1002 를 0120 으로 만들어야한다고 해보자. 한쪽만 필요한 색깔이 들어가도록 교환하면 1002->0012->0210->0120 의 결과가 된다. 양쪽이 모두 만족하는 교환을 먼저 시행하면 1002->0102->0120 으로 더 빠르다.

이러한 갯수를 세기 위해 BruteForce 를 수행할 수도 있다. O(N) 에 탐색을 마칠 수 있으므로 시간복잡도 상으로는 차이가 나지 않는다. 하지만 이를 수식적으로 풀 수도 있다.

• 한 줄을 그룹 0, 1, 2 로 나누고 그 안에는 0, 1, 2 만이 들어간다고 하자. 그리고 G(n, x) 를 n 그룹 안에 있는 초기 x 의 갯수라고 하자.
• G(0, 1) + G(0, 2) 만큼은 무조건 교환을 해야한다. 그러면 그룹 1 에는 1, 2 만이 담겨 있을 것이고, 이때 2 의 갯수는 G(1, 2) + 그룹 0 과 교환해서 얻은 2 로 나눌 수 있다. 이는 그룹 2 에도 똑같이 적용할 수 있다.
• 그룹 0 과 교환해서 얻은 2 같은 교환 부산물은 그리디하게 교환하면 한쪽에만 존재한다. 만약 그룹 0 과 교환해서 얻은 2 가 양수라면 G(1, 2) + 그룹 0 과 교환해서 얻은 2 = G(2, 1) 이 성립한다.
• 따라서 총 교환량은 G(0, 1) + G(0, 2) + max(G(1, 2), G(2, 1)) 이 된다.

이러한 전략를 사용할 수 있는 문제로 모양 정돈 이 있다.

시간 복잡도

O(\(\mathrm{N}\))

코드 2 (수식)

int n;
vector<int> arr[1001];

int MakeOrder(int patt[3])
{
	int res = 0;
	for (int i = 3; i <= n; i++)
	{
		int c[3][3]; fill(c[0], c[3], 0);
		int colors[3] = { patt[(i - 1) % 3], patt[(i) % 3], patt[(i + 1) % 3] };
		for (int s = 0; s < 3; s++)
			for (int j = s; j < i; j+=3)
				c[s][arr[i][j]]++;
		
		int div3 = (i - 1) / 3, mod3 = (i - 1) % 3;
		if (c[0][colors[0]] + c[1][colors[0]] + c[2][colors[0]] != div3 + 1)  return -1;
		if (c[0][colors[1]] + c[1][colors[1]] + c[2][colors[1]] != div3 + (mod3>=1))  return -1;
		if (c[0][colors[2]] + c[1][colors[2]] + c[2][colors[2]] != div3 + (mod3>=2))  return -1;

		res += c[0][colors[1]] + c[0][colors[2]] + max(c[1][colors[2]], c[2][colors[1]]);
	}

	return res;
}

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++)
		for (int j = 0; j < i; j++)
			cin >> arr[i].emplace_back();

	if (n == 1) cout << 0;
	else {
		int p[3] = { arr[1][0], arr[2][0], arr[2][1] };
		if (p[0] == p[1] || p[0] == p[2] || p[1] == p[2]) cout << -1;
		else {
			int r1 = MakeOrder(p);

			swap(p[1], p[2]);
			int r2 = MakeOrder(p);

			if (r1 == r2 && r2 == -1) cout << -1;
			else cout << min(r1, r2 + 1);
		}
	}
}

코드 2 (BruteForce)

int n;
vector<int> arr[1001], copys[1001]; 

int MakeOrder(int patt[3])
{
	int res = 0;
	for (int i = 3; i <= n; i++)
	{
		static int offsets[3][2] = { {1, 2}, {2, 0}, {0, 1} };
		int colors[3] = { patt[(i-1) % 3], patt[(i) % 3], patt[(i + 1) % 3] };
		for (int s = 0; s < 3; s++)
		{
			queue<int> mov1, mov2;
			for (int j = 0; j < i; j += 3)
			{
				if (j + offsets[s][0] < i && arr[i][j + offsets[s][0]] == colors[s])
					mov1.push(j+offsets[s][0]);
				if (j + offsets[s][1] < i && arr[i][j + offsets[s][1]] == colors[s])
					mov2.push(j+offsets[s][1]);
			} 
			for (int j = s; j < i; j += 3)
				if (arr[i][j] != colors[s])
				{
					if (mov1.empty() && mov2.empty())  return -1;				
					auto& mov = arr[i][j] == colors[(s + 1) % 3] ?
						(!mov1.empty() ? mov1 : mov2) :
						(!mov2.empty() ? mov2 : mov1);
					swap(arr[i][j], arr[i][mov.front()]);
					mov.pop();
					res++;
				}
			if (mov1.size() || mov2.size())  return -1;
		}
	}
	return res;
}

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++)
		for (int j = 0; j < i; j++)
			cin >> arr[i].emplace_back();

	if (n == 1) cout << 0;
	else {
		int p[3] = { arr[1][0], arr[2][0], arr[2][1] };
		if (p[0] == p[1] || p[0] == p[2] || p[1] == p[2]) cout << -1;
		else {
			for (int i = 1; i <= n; i++) copys[i] = arr[i];
			int r1 = MakeOrder(p);

			swap(p[1], p[2]);
			for (int i = 1; i <= n; i++) arr[i] = copys[i];
			int r2 = MakeOrder(p);

			if (r1 == r2 && r2 == -1) cout << -1;
			else cout << min(r1, r2 + 1);
		}
	}
}