[백준/BOJ] 백준 2450번 : 모양 정돈

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

2450번: 모양 정돈

세모, 네모, 동그라미가 어떤 순서로 배치되는지에 따라 각각 경우를 next_permutation를 통해 고려하고, 해당 경우로 구역을 나눴을 때 [도형a][도형b] = 개수 (도형a의 구역에 속해있는 도형b의 개수)를 세고, 이를 통해 도형1을 먼저 맞추고, 도형2,3을 맞추는 방식으로 문제를 해결했다.

 

코드

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

int n;
vector<int> inputs;
vector<int> cnt(4, 0);
int result = 987654321;

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int input;
		cin >> input;

		inputs.push_back(input);
		cnt[input]++;
	}

	vector<int> perm;
	for (int i = 1; i <= 3; i++)
		perm.push_back(i);

	do {

		//perm순서로 도형 배열할때 교체하는 횟수를 구한다

		//[도형a][도형b] = 개수 (도형a의 구역에 속해있는 도형b의 개수)
		vector<vector<int>> area_cnt(4, vector<int>(4, 0)); 

		int point_index = 0;
		for (int i = 0; i < 3; i++)
		{
			int this_cnt = cnt[perm[i]];

			for (int j = point_index; j < point_index + this_cnt; j++)
			{
				area_cnt[perm[i]][inputs[j]]++;
			}

			point_index = point_index + this_cnt;
		}

		int this_result = 0;

		//도형1이 들어가야 하는 위치에 있는 도형2,3을 도형1로 바꾸기 위한 교체 횟수
		this_result += area_cnt[1][2] + area_cnt[1][3];
		//도형2가 들어가야 하는 위치에 도형3이 들어 있는 도형3과, 도형3이 들어가야 되는 위치에 도형2가 들어있는 도형 2를 교환한다
		this_result += max(area_cnt[2][3], area_cnt[3][2]);

		result = min(result, this_result);

	} while (next_permutation(perm.begin(), perm.end()));

	cout << result << "\n";

	return 0;
}