티스토리 뷰

알고리즘/BOJ

BOJ 11399, ATM

아테즈 2019. 3. 25. 20:17

ATM 문제는 순서를 바꿔도 상관 없는 문제입니다.


직관적으로 탐욕법으로 풀 수 있다는 걸 눈치챌 수 있습니다.


하지만, 최적 부분구조가 성립하는지 증명을 해보도록 하겠습니다.


N명의 사람들이 서 있다고 할 때, 


우리가 정답으로 고른 순서가


S1, S2, S3, S4, S5라고 해봅시다.


그리고, S1>S2라고 가정해보겠습니다.


이때 걸리는 총 시간은


S1, S1+S2, S1+S2+S3, S1+S2+S3+S4, S1+S2+S3+S4+S5의 합입니다.


즉, 5*S1 + 4*S2 + 3*S3 + 2*S4 + 1*S5이 됩니다.


하지만, S1 > S2이므로, S1과 S2의 위치를 바꿔서 


5*S2 + 4*S1 + 3*S3 + 2*S4 + 1*S5로 계산하면 우리가 원래 정답으로 고른 순서보다


작은 답을 얻을 수 있습니다. 위 과정을 S(i-1), S(i)에 대해 모두 진행해보게 되면,


우리가 원하는 답은, 입력으로 주어진 p1, p2, ..., pn의 수열을 오름차순으로 정렬 한 다음


(p1부터 pi까지의 합)의 합을 구하면


우리가 원하는 답을 구할 수 있다는 것을


증명할 수 있습니다.



예제 입력 1 

5
3 1 4 3 2

예제 출력 1 

32


1 2 3 3 4

= 5*1 + 4*2 + 3*3 + 2*3 + 1*4

= 5+8+9+6+4 =32


따라서 답은 32,


시간복잡도는 정렬하는데 걸리는 시간 O(nlogn)에, 답을 구하는데 걸리는 시간 O(n)으로


총 O(nlogn)의 시간복잡도로 문제를 해결할 수 있습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int main() {
    vector<LL> v;
    LL n; scanf("%lld"&n);
    for (int i = 0; i < n; i++) { LL temp; scanf("%lld"&temp); v.push_back(temp); }
    sort(v.begin(), v.end());
    LL sum = 0;
    for (int i = 0; i < v.size(); i++) {
        sum += (v.size()-i)*v[i];
    }
    cout << sum;
    return 0;
}
cs

 

'알고리즘 > BOJ' 카테고리의 다른 글

BOJ 1541, 잃어버린 괄호  (0) 2019.03.25
BOJ 1931, 회의실 배정  (0) 2019.03.25
BOJ 11399, ATM  (0) 2019.03.25
BOJ 7576, 토마토  (0) 2018.10.22
BOJ 14731번, 謎紛芥索紀 (Large) - (미분개색기)  (0) 2018.10.20
BOJ 11047번, 동전 0  (0) 2018.10.20
댓글
댓글쓰기 폼
공지사항
Total
21,136
Today
0
Yesterday
27
링크
TAG
more
«   2022/07   »
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
글 보관함