https://www.acmicpc.net/problem/11399
문제
> 은행에 ATM이 1대 뿐이라 번호가 매겨진 N명이 줄을 서있다.
> i번 사람이 인춯하는데 pi분이 걸릴 때 줄 서는 순서에 따라 필요한 시간이 달라진다.
> P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우 [1, 2, 3, 4, 5] 순서로 줄을 선다면
> 1번 사람은 3분, 2번 사람은 3+1 = 4분, 3번 사람은 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다.
> 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.
> 줄을 서 있는 사람의 수 N과 걸리는 시간 Pi가 주어졌을 때, 돈을 인출하는데 필요한 시간의 합의 최솟값을 구해라.접근
인출하는데 걸리는 시간의 합이 최소가 되려면 각각 걸리는 시간이 최소가 되어야한다. 그러기 위해선 걸리는 시간이 짧은사람부터 빨리빨리 끝내주고 나가야 병목현상이 일어나지 않는다. 입력받은 걸리는 시간을 기준으로 오름차순으로 정렬하고 계산식을 정의해 출력하면된다.
문제해결
> 인덱스를 1부터 주기 위해 vector를 N+1크기로 선언하고 문제에 주어진 입력을 모두 처리한다.
> 시간이 짧게 걸리는 사람부터해야 최소값이 나오므로 오름차순으로 정렬해준다. 정렬된 vector를 새로운 벡터에 담는다.
> 누적합 방법을 사용해 i번째 사람이 걸리는 시간을 누적해서 구하고 해당 값을 sum에 계속 누적해 총 누적합을 구한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<int>P(N+1);
for (int i = 1; i <= N; i++) cin >> P[i];
sort(P.begin(), P.end());
vector<int>newP = P;
long long sum = 0, prefix = 0;
for (int i = 1; i <= N; i++)
{
prefix += newP[i];
sum += prefix;
}
cout << sum << '\n';
}
후기
처음에 누적합 부분을 이중for문으로 해서 구현했다. 정답은 맞았지만 보통 이런 합이나 연속된 문제는 점화식이 있거나 연산을 줄이는 방법이 있다. 그래서 찾아보니 누적합 방법을 알게 됐다. 이중 반복문을 쓰면 시간 복잡도가 O(N^2)이 나온다. 하지만 누적합을 쓰면 O(N)이므로 훨씬 줄어든다.
한번의 반복문안에서 i번째 사람이 걸리는 시간과 총 합을 한번에 누적하는것이다.
왜 이 생각을 못헀지..
