백준 11399 풀이

링크텍스트

너무 복잡하게 생각해서 손해를 본 문제였다.

사람들이 한 대의 ATM을 이용하는데 걸린 시간이 최소가 되도록 해야 하기때문에 그리드로 풀 생각을 했다.
그런데 중간에 쓸데 없는 생각을 한 번 더해 그리드가 아닌 다른 방법으로 풀었다.

사람이 있고 사람마다 사용하는 시간이 있으니 이 부분을 고려해야할까?

시작된 생각은 점점 삼천포로 빠져 엉뚱한 풀이를 하게 만들었다.
처음에 풀었던 방법은 그래서 모든 경우의 수를 통해 시간을 구해 최소를 찾는 브루트 포스 방법이었다. 당연히 시간 초과를 맞이했고 알고리즘을 수정해야했다.

결국 생각을 단순화하여 문제를 다시 보니 그냥 주어진 이용 시간을 오름차순으로 정렬하여 누적하여 합을 구하면 끝나는 문제였다.

#include <iostream>
#include <deque>
#include <vector>
#include <string>
#include <string.h>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <utility>
using namespace std;

int n;
int m;
bool visited[1001] = { 0, };
int arr[1001];
int queue[1001];
int minSum = 1000000;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int answer = 0;
	cin >> n;
	vector<int> v;
	
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	sort(v.begin(), v.end());
	int wait = 0;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		sum = sum + wait + v[i];
		wait = wait + v[i];
	}

	cout << sum << '\n';
	return 0;
}

알고리즘 문제를 풀 때마다 생각을 너무 단순하게 하여 문제를 접근할 때가 많았는데 이번에는 너무 복잡하게 생각해서 꼬였던 문제였다.