백준 5000번 빵정렬

문제링크: https://www.acmicpc.net/problem/5000

사용한 알고리즘: 수학



먼저 inversion 이라는 개념에 대해 말씀드리겠습니다.
inversion이란 쉽게말해 어떤 permutation에서 큰수가 작은수 앞에 있는 경우의 쌍의 수입니다. 예를들어 4312 라는 permutation이 주어지면 이것의 inversion은 (4,3),(4,1),(4,2),(3,1),(3,2) 로 총 5개입니다.
이제 우리는 어떤 permutation의 inversion을 modulo 2 에서 생각할 것입니다.
생각해야 하는 점은 어떤 permutation a1, a2, a3, ... , a10 을 생각해 봤을 때,
a1 과 a10의 순서를 맞바꾸어 a10, a2, a3, ... , a1 으로 만들었을 때 이 permutation의 inversion 성질은 정 반대가 됩니다. (mod 2 에서 0 아니면 1 입니다. 즉 0이였으면 1이됩니다.) 잘 생각해보면

(1) a1과 a10 사이의 수들에 대한 a1과 a10의 inversion은 변함이 없습니다. 쉽게 다시 생각하여 a b c 의 permutation이 주어지고 이를 c b a 로 바꾸었다 생각해봅시다. a, b, c 의 대소에 상관없이 a, b 가 b, a가 될때 발생하는 inversion 변화와 b, c 가 c, b 가 될 때 발생하는 inversion 변화는 서로 상쇄됩니다. 예를들어 a < b < c 인 경우(어떠한 경우라도 다 성립됩니다. 그냥 예를 하나 잡은겁니다.) a b c 가 c b a 가 될 때 b, c 가 c, b 가 되므로(c>b) inversion+1, a, b 가 b, a가 되므로 inversion+1 로 토탈 +2 = 0(mod 2) 입니다. 위와같은 이유로 양 끝을 바꿀 때 중간에 있는 값들과의 관계는 생각할 필요 없습니다.

(2) a1과 a10 의 대소에 관계없이 a1과 a10의 순서가 바뀌므로 inversion의 성질이 반대가 됩니다. 사이 수들 혹은 a1,a10 밖의 수들과의 관계는 과정 (1) 에 의해 생각 안해도 된다고 말씀드렸습니다.

(3) 빵 나열 규칙을 통해 빵의 순서를 바꾸는 경우는 (mod 2 에서) inversion이 유지되는 모든 경우입니다. 잘 생각해보면 a b c 가 c a b 가 되는 경우는 inversion이 유지되는 모든 경우라는걸 알 수 있겠죠?

위와 같은 이유로 주어진 빵의 순서와 만들고 싶은 빵의 순서의 inversion 성질이 같은지 여부로 만들 수 있나 없나를 판단할 것입니다. 즉, 주어진 빵 순서에서 만들고자하는 빵 순서로 만들기 위해서 몇번이나 빵의 위치를 바꾸어야 하는지 세고, 빵을 한번 바꿀때 마다 inversion 성질이 바뀌므로 짝수번 바꿔야한다면 만들 수 있고, 홀수번 바꾸어야 한다면 만들 수 없다고 판단 가능합니다.

굉장히 부실한 설명 죄송합니다... 찰떡같이 이해해주시길.....

	#include <bits/stdc++.h>
	using namespace std;
	int N, cnt, now[100001], goal[100001];
	map<int, int> where;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	cin >> N;
	for (int i = 0; i < N; ++i){
	cin >> now[i];
	where[now[i]] = i;
	}
	for (int i = 0; i < N; ++i) cin >> goal[i];
	for (int i = 0; i < N; ++i){
	int w = where[goal[i]];
	// 맞는 위치에 있으면 패스
	if(w==i) continue;
	// now[i] <-> now[w] 위치 바꾸기, where[goal[i]] = i 는 써줄필요 없자나 ( 뒤에서 안보니 그냥 생각만 해줘 )
	now[w] = now[i];
	where[now[w]] = w;
	cnt++;
	}
	if(cnt%2==0) cout << "Possible" << '\n';
	else cout << "Impossible" << '\n';
	return 0;
	}

view raw BOJ 5000.cpp hosted with ❤ by GitHub