티스토리 뷰

알고리즘 관련/BOJ

BOJ)14943 벼룩 시장

JASON 자손9319 2017. 12. 18. 04:06

문제: icpc.me/14943

벼룩을 사려는 사람과 팔려는 사람이 있을 때 벼룩 거래에 발생하는 비용의 최솟값을 출력하는 문제이다.

문제를 잘 읽어보면 사려는 양과 팔려는 양은 같고, 거래에 발생하는 비용이 거래하는 두 사람의 거리에 비례한다.

우선 사려는 양과 팔려는 양이 같다는 점을 이용해, 항상 거래가 완전하게 이루어진다는 점을 생각해보면, 그냥 최대한 가깝게 거래를 매칭 시켜주는 그리디한 방법이 답이 된다는 걸 알 수 있다.

문제는 n이 10만으로 조금 크기 때문에 매칭을 일일이 직접 해줄 수는 없고, 투 포인터를 이용하여 처리해주면 깔끔하게 구현 가능하다.

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
32
33
34
35
36
37
38
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
ll n,a[111111],res;
int main(){
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);
    int idx=0;
    for(int i=1;i<n;){
        while(!a[idx])idx++;
        if(i==idx){
            i++;
            continue;
        }
        if(a[idx]*a[i]>=0){
            i++;
            continue;
        }
        if(abs(a[idx])>=abs(a[i])){
            res+=abs(a[i]*(idx-i));
            a[idx]+=a[i];
            a[i]=0;
            i++;
        }
        else{
            res+=abs(a[idx]*(idx-i));
            a[i]+=a[idx];
            a[idx]=0;
        }
    }
    printf("%lld\n",res);
    return 0;
}
 
 
cs


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

BOJ)15673 헤븐스 키친2  (1) 2018.05.06
BOJ)2171 직사각형의 개수  (0) 2017.12.19
BOJ)14943 벼룩 시장  (0) 2017.12.18
BOJ)14950 정복자  (0) 2017.12.12
BOJ)15271 친구 팰린드롬2  (0) 2017.12.05
BOJ)15270 친구 팰린드롬  (0) 2017.12.05
댓글
댓글쓰기 폼