취미로 코딩하기

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

이번에 볼 문제는 백준 24620번 문제인 Sleeping in Class이다.
문제는 아래 링크를 확인하자.

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

최종 배열에 남는 수들은 모두 동일하므로, 그 수는 주어진 수열의 모든 수의 총합의 약수가 되어야 함을 관찰하자.

특히, 모든 수를 다 합치면 하나의 수만 남으므로 문제의 답은 항상 존재함을 알 수 있다.

모든 총합의 약수에 대하여 그 수만이 최종배열에 남게 수를 합칠 수 있는지 배열을 앞에서부터 읽어나가며 확인해나가자. 그리고 그 중 가능한 약수에 대하여 그 수만 남길 때 필요한 연산의 횟수의 최솟값을 구해 문제를 해결하자.

주어진 수의 총합은 100만을 넘기지 않으므로, k가 총합의 약수이면 (총합/k) 또한 총합의 약수임을 이용해 k를 1부터 1000까지 살피는 것으로 모든 약수에 대한 탐색을 진행할 수 있다.

주어진 세 번째 예제와 같이 총합이 0인 경우에 유의해 구현해주자.

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

#include <iostream>
using namespace std;

int T, N;
int arr[100000];
int total;

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

	cin >> T;
	while (T--) {
		cin >> N;
		total = 0;
		for (int i = 0; i < N; i++) {
			int& x = arr[i];
			cin >> x;
			total += x;
		}

		if (total == 0) cout << 0 << '\n';
		else {
			int ans = 1000000007;
			for (int k = 1; k < 1001; k++) {
				if (total % k) continue;
				int cnt = 0, psum = 0;
				for (int i = 0; i < N; i++) {
					psum += arr[i];
					if (psum > k) {
						cnt = 1000000007;
						break;
					}
					else if (psum < k) cnt++;
					else psum = 0;
				}
				ans = min(ans, cnt);

				int kk = total / k;
				cnt = 0, psum = 0;
				for (int i = 0; i < N; i++) {
					psum += arr[i];
					if (psum > kk) {
						cnt = 1000000007;
						break;
					}
					else if (psum < kk) cnt++;
					else psum = 0;
				}
				ans = min(ans, cnt);
			}

			cout << ans << '\n';
		}
	}
}