2405

상당한 아이디어를 요구하는 것 같은 문제이나 실제로 푸는 방법은 간단하다.

N이 최대 1000이기 때문에 가능한 모양 순열 123, 132, 213, 231, 312, 321 의 가정답을 나열한 다음 원래 주어진 모양 순열에서 가정답으로 바꿀 때 각각의 최소 횟수를 구해 전체 최소 횟수를 구할 수 있다.

각 모양은 최소 한 번 이상 나타난다는 조건으로 문제 풀이에 살짝 힌트를 주었다.

최소 횟수를 구하는 것은 간단하다. 여기서는 3가지 모양 밖에 없다는 사실을 잘 이용하자.

 
#include<cstdio>
#include<algorithm>

using namespace std;

int data[100005];
int res_arr[100005];
int d[4];

int main(){
	int N, ret;
	scanf("%d", &N);

	ret = N;

	int order[3] = {1, 2, 3};

	for(int i=0; i<N; i++){
		scanf("%d", &data[i]);
		d[data[i]]++;
	}

	do{
		int res = 0;
		int rem = 0;
		
		int piv=0;
		for(int i=0; i<3; i++){
			for(int j=0; j<d[order[i]]; j++)
				res_arr[piv++]=order[i];
		}

		int a[4][4]={0};

		for(int i=0; i<N; i++)
			if(data[i]!=res_arr[i])
				a[data[i]][res_arr[i]]++;

		for(int i=1; i<3; i++)
			for(int j=i+1; j<=3; j++)
			{
				if(a[i][j] > a[j][i])
				{
					res += a[j][i];
					rem += a[i][j] - a[j][i];
				}
				else
				{
					res += a[i][j];
					rem += a[j][i] - a[i][j];
				}
			}

		res += (rem/3)*2;
		ret = min(res, ret);
	}while(next_permutation(order, order+3));

	printf("%d\n", ret);

	return 0;
	
}