[BOJ 25181] 백준 25181번 - Swap the elements

		2022 서강대학교 청정수컵 풀이
A		[BOJ 25175] 두~~부 두부 두부
B		[BOJ 25176] 청정수열 (Easy)
C		[BOJ 25177] 서강의 역사를 찾아서
D		[BOJ 25178] 두라무리 휴지
E		[BOJ 25179] 배스킨라빈스~N~귀엽고~깜찍하게~
F		[BOJ 25180] 썸 팰린드롬
G		[BOJ 25181] Swap the elements
H		[BOJ 25182] 청정수열 (Hard)
I		[BOJ 25183] 인생은 한 방
J		[BOJ 25184] 동가수열 구하기
K		[BOJ 25185] 카드 뽑기
L		[BOJ 25186] INFP 두람
M		[BOJ 25187] 고인물이 싫어요
N		[BOJ 25188] 1, 3, 모 나누기

1. 문제

$25181$. Swap the elements (2022 서강대학교 청정수컵 G번)

백준 25181번 - Swap the elements (https://www.acmicpc.net/problem/25181)

2. 풀이

어떤 숫자의 개수가 배열 길이의 절반보다 많으면, 숫자들을 어떻게 배치해도 $A_i==B_i$인 $i$가 하나 이상 생길 수 밖에 없다. (비둘기집 원리) 따라서 모든 숫자의 개수에 대해서 이를 확인하면, $B$ 배열을 만들 수 있는지 없는지를 알아낼 수 있다.

$B$ 배열을 만들 수 있다면, $A$ 배열의 어떤 숫자의 개수는 배열 길이의 절반보다 작다. 따라서 $A$ 배열을 오름차순으로 정렬하였을 때, $A[i]$와 $A[i + N / 2]$는 무조건 서로 다른 수이다.

위 사실을 이용하여 모든 $i$에 대해 $A[i]$와 $A[i + N / 2]$를 바꾸면(이미 바꿔진 수는 제외), $B$ 배열을 구할 수 있다.

3. 채점 결과

4. 회고

$B$ 배열을 만드는 것이 가능한지에 대한 여부는 금방 떠올렸으나, $B$ 배열을 만드는 방법을 쉽게 생각해내지 못했다.

여러 방법을 시도해봤으나, 모두 WA나 TLE를 받는 불완정한 방법이었고, 나중에서야 $B$ 배열의 가능 여부에 힌트가 있다는 사실을 알 수 있었다.

5. 코드