[C++] 백준 2117번: 원형 댄스

문제 링크

2117번: 원형 댄스

문제 요약

N명의 사람이 원형으로 서 있다. 이 사람들은 순서대로 1 ~ N까지의 번호를 가지고 있는데, 자리를 최소한으로 바꿔서 N ~ 1까지 역순으로 나열되도록 해야 한다. 이 때, 자리 교환 횟수의 최솟값을 구해야 한다.

접근 방법

N명의 사람들을 절반으로 나눠서, 2개의 집합을 만들고 생각할 수 있습니다.

(1, 2, 3, 4, 5, 6)

이렇게 사람들이 있을 때, 양 끝단에 가까운 사람들은 이 사람들끼리만 자리를 교환하고 나머지 사람들 역시 그 사람들끼리만 자리를 교환합니다. 따라서 (1, 2, 6)끼리만 자리를 교환하고, (3, 4, 5)끼리만 자리를 교환합니다.

1, 2, 3
1, 3, 2
3, 1, 2
3, 2, 1

교환은 위와 같이 진행이 됩니다. 따라서 이 때의 교환 횟수는 집합의 크기를 N이라고 할 때, $\sum\limits_{i = 1}^{N - 1}i$가 됩니다.

이걸 이용하면 쉽게 문제를 풀 수 있습니다. N을 입력 받으면 N / 2와 N - (N / 2)를 구합니다. 이 둘을 각각 K, L이라고 할 때, $\sum\limits_{i = 1}^{K - 1}i+\sum\limits_{i = 1}^{L - 1}i$을 구해주면 됩니다.

사실 제 경우에는 그냥 규칙을 바로 발견해서 코드는 규칙대로 작성을 했습니다.

1 : 0
2 : 0
3 : 1
4 : 2
5 : 4
6 : 6
7 : 9
8 : 12
9 : 16
10 : 20
11 : 25
12 : 30

1부터 12까지 답을 구한 것입니다. 보시면 4부터 6까지 값은 2씩 증가를 합니다. 그 다음 6부터 8까지는 3씩, 8부터 10까지는 4씩, 10부터 12까지는 5씩 증가하는 것을 볼 수 있습니다. 저는 이 규칙을 이용해서 코드를 작성했습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n;
	cin >> n;

	if (n <= 3)
	{
		cout << (n <= 2 ? 0 : 1);
		return 0;
	}

	int res = 2, val = 2;
	for (int i = 5; i <= n; i++)
	{
		res += val;
		if (i % 2 == 0) val++;
	}

	cout << res;
	return 0;
}