[백준 11399] ATM (C++)

1. 문제

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

11399번: ATM

 

2. 접근 방법

그리디를 떠올릴 수만 있다면 아주 쉬운 문제입니다. 하지만 그리디를 떠올리기 쉽지 않으므로 항상 일관된 알고리즘적 사고가 필요한 것 같습니다. 따라서 평소처럼 일관된 방법으로 접근했습니다.

아이디어

1. 완전 탐색으로 생각해볼 때 나올 수 있는 모든 가지수는 1000!입니다. 팩토리얼의 허용 범위는 11이므로 불가능합니다.
2. 완전 탐색이 불가능하여 DP로 접근해보았습니다. 이 문제의 조건을 보니 조합이 아니라 순열입니다. 즉, 데이터의 순서가 중요합니다. 쉽게 말해서 i번째 값을 넣고/안넣고의 가지수를 탐색하는 것이 아니라 i번째 데이터가 어느 자리에 들어가는지가 이후에 큰 영향을 미칩니다. 결국 DP로 풀어도 1000! 가지수의 배열칸이 필요하다는 것을 알 수 있습니다. 
3. 혹시 그리디가 아닐까 의심해보고 인출 시간이 작은 값이 앞에올수록 전체 합은 작아진다 라는 가설을 세워봤습니다. 시뮬레이션 결과 반례가 존재하지 않는 것 같아 그대로 진행했습니다.

풀이

그리디를 떠올리기만 했다면 풀이는 간단합니다. sort함수를 이용하여 데이터를 오름차순으로 정렬한 뒤 누적합을 구해주기만 하면 됩니다.

 

3. 코드

#include<iostream>
#include<algorithm>

using namespace std;
int N, sum, ans;
int p[1001];
int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> p[i];
	sort(p, p + N + 1);

	//solve
	for (int i = 1; i <= N; i++) {
		sum += p[i];
		ans += sum;
	}
	cout << ans;
	return 0;
}