취미로 코딩하기

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

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

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

주어진 N개의 수 중 N-1개의 수를 합해 나올 수 있는 경우의 수를 첫번째 줄에 출력하고, 그 때의 각 합을 크기순으로 다음 줄에 출력하는 문제이다.

매번 N-1개의 수를 더하는 것은 O(N^2)의 시간복잡도를 가져 느리므로, N개의 수를 모두 더한 값을 계산한 뒤 각 N가지의 수를 해당 수에서 빼는 식으로 구현해 시간복잡도를 O(N)으로 줄이자.

set을 이용하면 중복원소를 빼고 원소들을 저장해주므로 문제에서 요구하는 내용을 간단히 구현할 수 있다.

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

#include <iostream>
#include <set>
using namespace std;

set<int> st;

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

	int total = 0;
	int N; cin >> N;
	while (N--) {
		int x; cin >> x;
		st.insert(x);
		total += x;
	}

	cout << st.size() << '\n';
	for (auto iter = st.rbegin(); iter != st.rend(); iter++) {
		cout << total - (*iter) << ' ';
	}
}