[BOJ 25637 // C++] 회전 목마

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

 

이번에 볼 문제는 백준 25637번 문제인 회전 목마이다.
문제는 아래 링크를 확인하자.

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

25637번: 회전 목마

회전 목마가 원형이 아닌 선형인 경우 이 문제는 greedy해법이 잘 알려져있다.

 

사람을 최소횟수로 옮기는 경우 주어진 회전목마의 각 목마 사이들 중 "사람의 이동이 발생하지 않은" 목마 사이가 존재할 수밖에 없음을 관찰하자. 또한 그 경우, 그 부분을 원형에서 끊은 선형에서의 greedy해법과 사람을 옮기는 방법이 동일하다는 점을 관찰하자.

 

따라서, 모든 가능한 회전목마 사이를 끊어 각 N가지 경우에 대해 답을 구한 뒤 그중 최솟값을 출력하는 것으로 문제를 해결할 수 있다.

 

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

#include <iostream>
using namespace std;

int N;
int arr[4000];
int ans = 1000000007;

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		arr[i + N] = arr[i];
	}

	for (int i = 0; i < N; i++) {
		int tmp = 0, cnt = 0;
		for (int j = 0; j < N; j++) {
			int arrij = arr[i + j];
			while (arrij--) {
				tmp += abs(j - cnt);
				cnt++;
			}
		}

		ans = min(ans, tmp);
	}

	cout << ans;
}