[BOJ 25184] 백준 25184번 - 동가수열 구하기

		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. 문제

$25184$. 동가수열 구하기 (2022 서강대학교 청정수컵 J번)

백준 25184번 - 동가수열 구하기 (https://www.acmicpc.net/problem/25184)

2. 풀이

서로 이웃한 원소의 차가 $floor(N/2)$ 이상이어야 한다. 따라서, $i$와 $i + N / 2$ 두 수를 붙이는 것이 효율적이다.

$N=6$일 때를 생각해보자.

$1$과 $4$를 붙이고, $2$와 $5$를 붙이고, $3$과 $6$을 붙이면 된다. 단순하게 배열하면 $142536$이 된다.

그러나, $142536$은 중간의 이웃한 원소 차가 $2(\leq N/2)$인 경우가 있다. 따라서 다른 배열 방법이 필요하다.

$1->2->3$ 순서로 배열하는게 아니라, $3->2->1$ 순서로 배열하면, $362514$가 된다. 이렇게 하면 인접한 수들이 최대한 멀어져서, 모든 이웃한 원소의 차가 $3$ 이상임을 확인할 수 있다.

따라서, $N / 2$부터 $1$까지 점점 감소하는 $i$에 대해서, $i$와 $i + N / 2$를 출력하면 정답 수열이 도출된다.

단, $N$이 홀수인 경우는 $N$ 하나가 수열에 빠져서 맨 마지막에 이를 추가해줘야 한다.

3. 채점 결과

4. 회고

.

5. 코드