본문 바로가기

알고리즘 관련/BOJ

BOJ)14943 벼룩 시장

문제: 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)14950 정복자  (0) 2017.12.12
BOJ)15271 친구 팰린드롬2  (0) 2017.12.05
BOJ)15270 친구 팰린드롬  (0) 2017.12.05