Boj 25559) 패스

문제

백준 25559

설명

문제를 재해석하면 [1, n] 까지의 수를 어떤 순서대로 더했을 때 Mod 값이 0 부터 n-1 까지 한번씩 나와야한다는 것이다.

n 이 우선 1보다 큰 홀수일 때를 생각해보자. [1, n] 까지의 합은 n(n+1)/2 인데 n 이 홀수이므로 전체 합은 n 으로 나누어 떨어진다. 또한 여기서 n 을 빼도 나누어 떨어진다. 그러면 n 을 제외하고 임의로 순서를 정했을 때 그 순서 사이에 n 을 넣으면 무조건 하나가 중복됨을 알 수 있다. 따라서 불가능하다.

n 이 짝수일 때를 생각해보자. 여기서 [1, n] 까지의 수의 합을 구하는 공식과 비슷한 아이디어로, 두 수의 Mod 값이 1 이 되도록 카드 두개씩 짝짓는 발상을 할 수 있다. 그러면 MOD 값을 1, 2, 3 ... n-2, n-1, 0 에서 맨 뒤와 맨 앞에서 차례로 값을 들고 올 수 있다. 이때 두 수의 거리가 1 이 아니라 2 씩 줄어드므로 주의하자.

시간 복잡도

O(\(\mathrm{N}\))

코드

int main(void)
{
	int n; cin >> n;
	if (n == 1) cout << 1;
	else if (n & 0b1) cout << -1;
	else {
		for (int i = 1; i <= n; i += 2)
			cout << n - i + 1 << ' ' << i << ' ';
	}
}