[C++][그리디 - ATM(11399)]

백준/그리디/ATM 바로가기

 

 

체점 현황

 

[문제 설명]

단순 누적 문제다.

 

 

[소스 코드]

#include <bits/stdc++.h>

using namespace std;
int main(){ 
	int n,res=0,tmp;
	vector<int> wt;
	cin>>n;	
	for(int i = 0 ; i < n ; i++){
		cin>>tmp;
		wt.push_back(tmp);
	}
	sort(wt.begin(),wt.end());
	tmp = 0;
	for(int elem : wt){
		tmp += elem;
		res += tmp;
	}
	cout<<tmp;
	return 0;
}

 

[해결 전략]

문제를 읽어 보니 누적 시간의 최솟값을 구하는 문제였다.

입력 받고 정렬 시킨 다음 누적 시간의 합을 구했다.

 

 

[시간 복잡도]

데이터 개수가 n개라 할때

sort 하는데 걸리는 시간이 얼마가 될지 O(n log n) 이라면

시간 복잡도도 O(n log n)이다

 

 

[다른 사람 풀이]

for(int i = 0; i < n ; i++){
	res += wt[i]*(n-i);
}

같은 맥락이지만 sort 후 더해지는 횟수를 바로 곱해서 res에 더했다.

ex) {1,2,3,4,5} 라면 1은 5번 더해지고 2는 4번 이런식으로 진행되기 때문에

 

 

[참고]

https://seoftware.tistory.com/29