BOJ 2450 - 모양 정돈 (KOI 중등 , 구현)

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

 

최소한으로 이동하는 방법을 생각해 내지 못했다..

 

정렬이 이뤄지면 결과적으로 6개의 가능한 모양이 있다. (1,2,3의 순열)

 

이 때 최소한으로 움직이는 방법을 살펴보면

 1. 그룹(1)에 있는 그룹(2)(3)에 속해야 하는 요소들의 개수 (그룹(2),(3)에 속한 그룹(1)요소의 개수와 같다)

    (ex 입력이 1223111, (1,2,3)순서라면 2+1)

 2. 그룹(2)에 있는 그룹(3)요소의 개수, 그룹(3)에 있는 그룹(2) 요소의 개수; 둘 중 큰 것

1,2를 더해주면 최소한으로 움직이는 횟수가 된다.

 

복잡해보이지만, 그룹1먼저 채워주고 그룹2,3을 생각해주는 것이다.

 

생각하는 과정에서 스쳐가듯 생각한 방법이긴 하지만, 이 방법이 유효하지 않은 경우가 있을 것 같아서 제꼈다. 푼 사람들 중에 이 논리를 검증한 사람이 있을까? 아니면 검증하지 않아도 당연한 논리인걸까?

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int INF = 1e9;

vector<int> vec;
int cnt[4], p[3] = { 1,2,3 };

int main() {
	int n; cin >> n;
	for (int i = 0, input; i < n; i++) {
		cin >> input;
		vec.push_back(input);
		cnt[input]++;
	}

	int mn = INF;
	do {
		int arr[4][4] = { 0 }; //p[i]번 위치의 j의 개수

		int sp = 0;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < cnt[p[i]]; j++) 
				arr[p[i]][vec[sp + j]]++;
			sp += cnt[p[i]];
		}

		mn = min(mn, arr[1][2]+arr[1][3]+max(arr[2][3],arr[3][2]));
	} while (next_permutation(p, p+3));

	cout << mn << '\n';
}

arr를 채워주는 논리를 짜는 것도 쉽지만은 않았다.

 

mn 갱신하는 부분에서 arr[p[1]][p[2]]로 하지않고 1,2,3 숫자로 고정한 이유는 조금만 생각해 보면 될 것이다.

(그룹만 잘 나눠줬다면 위에 설명한 논리에 들어가는 숫자 순서를 바꿔도 되기 떄문. 그룹2부터채우고 1,3을 채운다던지)