취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6496번 문제인 Cyclic antimonotonic permutations이다.
문제는 아래 링크를 확인하자.

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

주어진 규칙을 만족하는 순열을 찾는 규칙찾기 문제이다.

주어지는 정수 n의 제한이 100만으로 제법 크고 여러 테스트케이스를 처리해야하므로 선형 시간복잡도로 답안을 생성할 수 있는 규칙을 적어도 하나 이상 찾아내 문제를 풀어야한다.

글쓴이는 왼쪽에서 오른쪽으로는 홀수번째 항들을 이용해 규칙적으로 이동하고, 오른쪽에서 왼쪽으로는 짝수번째 항들을 이용해 규칙적으로 이동하는 방식의 답 생성규칙을 하나 발견해 코드를 작성하였다. 이 외에도 많은 답이 있을 수 있으니 직접 규칙을 찾아보며 재미를 느껴보자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int N;

void solve() {
	if (N & 1) {
		while (N > 1) {
			cout << N - 1 << ' ' << N << ' ';
			N -= 2;
		}
		cout << 1 << '\n';
	}
	else {
		cout << 3 << ' ' << 1 << ' ';
		int idx = 5;
		while (idx < N) {
			cout << idx << ' ' << idx - 3 << ' ';
			idx += 2;
		}
		cout << N << ' ' << N - 2 << '\n';
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie();

	cin >> N;
	while (N) {
		solve();
		cin >> N;
	}
}