[BOJ 24818 // C++] Field Trip

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

 

이번에 볼 문제는 백준 24818번 문제인 Field Trip이다.
문제는 아래 링크를 확인하자.

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

24818번: Field Trip

주어진 학생들 section들을 연속하게 세 그룹으로 잘라 각 버스에 탑승하는 학생의 수가 모두 같게 할 수 있는지를 묻는 문제이다.

 

전체 학생의 수 total이 3의 배수가 아니거나, total이 3의 배수지만 total/3씩 앞에서부터 셋으로 자를 수 없다면 -1을, 그렇지 않다면 첫번째와 두번째 버스에 탑승하게 되는 가장 마지막 학생의 section의 인덱스를 출력해주자.

 

전체 학생 수가 100억명까지 나올 수 있다는 점에 유의하자.

 

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

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

ll arr[1000000];
vector<ll> ans;

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

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

	if (total % 3) cout << -1;
	else {
		total /= 3;
		ll psum = 0;

		for (ll i = 0; i < N; i++) {
			psum += arr[i];
			if (psum == total) ans.emplace_back(i + 1), psum = 0;
		}

		if (ans.size() == 3) cout << ans[0] << ' ' << ans[1];
		else cout << -1;
	}
}