8004 : 아름다운 순열
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 15
•통과: 1
•만든사람: suakii
문제 설명
정수 $N$이 주어질 때, $1$부터 $N$까지의 수를 각각 한 번씩 사용하여 인접한 두 원소의 차이의 절댓값이 1이 되지 않도록 배열을 만드시오.
만약 이러한 아름다운 순열이 존재하지 않는다면
[제약 조건]
• $1 \le N \le 10^6$
만약 이러한 아름다운 순열이 존재하지 않는다면
NO SOLUTION을 출력하십시오.[제약 조건]
• $1 \le N \le 10^6$
입력 설명
첫째 줄에 정수 $N$이 주어집니다.
출력 설명
조건을 만족하는 순열을 공백으로 구분하여 한 줄에 출력합니다.
조건을 만족하는 순열이 여러 가지인 경우 그 중 아무거나 하나를 출력합니다.
만약 조건을 만족하는 순열이 존재하지 않는다면
조건을 만족하는 순열이 여러 가지인 경우 그 중 아무거나 하나를 출력합니다.
만약 조건을 만족하는 순열이 존재하지 않는다면
NO SOLUTION을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2 4 1 3 5도움
$N=1$일 때는
$N=2, 3$일 때는 인접한 원소의 차이가 1이 아닌 순열을 만들 수 없으므로
$N \ge 4$일 때는 모든 짝수를 오름차순으로 먼저 나열(
1이 유일한 해입니다.$N=2, 3$일 때는 인접한 원소의 차이가 1이 아닌 순열을 만들 수 없으므로
NO SOLUTION입니다.$N \ge 4$일 때는 모든 짝수를 오름차순으로 먼저 나열(
2 4 6 ...)한 후, 모든 홀수를 오름차순으로 나열(1 3 5 ...)하면 인접한 두 수의 차이가 항상 2 이상(짝수 간 차이 2, 홀수 간 차이 2, 짝수와 홀수의 연결 지점 차이 $|(\text{마지막 짝수}) - 1| \ge 3$)이 되어 손쉽게 아름다운 순열을 구성할 수 있습니다.