BOJ 7578 공장

 

문제 링크 : https://www.acmicpc.net/problem/7578

7578번: 공장

 

입력 순서와 값의 크기의 순서가 역전된 횟수를 '전도의 수(number of inversion)' 라고 한다.

원래 전도의 수를 세는 것이 ps에서 중요한 소재인 것인지는 잘 모르겠지만 boj에서는 많이 보게 된다.

기본적인 것으로 BOJ 1517 버블소트 를 들 수가 있겠다.

 

크기를 비교해서 역전된 것을 교환하는 횟수를 요구하는 시간 내에 해결하는 방법은 많다.

우선 sort 과정에서 비교와 교환 횟수를 구할 수 있는데,  

merge sort 처럼 $O(n\log n)$ 알고리즘은 무엇이든 가능하다.

 

하지만 segment tree나 BIT를 쓰는 것이 더 힘들지는 않으니 여기서는 BIT를 쓴다.

이런 유형의 문제들은 주어진 상황에 맞춰

1. 입력되는 순서대로 값의 크기에 대당하는 위치를 갱신할 수도 있고,

2. 반대로 값을 정렬하여 값의 크기 순으로 입력 위치를 갱신하는 방식을 사용할 수도 있다.

 

본 문제 BOJ 공장 7578 은 식별 번호를 입력 순서에 mapping 하는 것을 제외하면 기본형의 문제로 환원된다.

 

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

int sz;

map<int,int> mp;
int bits[500001];

void upd(int p, int v=1){
    for(;p<=sz;p+=p&-p)
        bits[p]+=v;
}

int qry(int p){
    int res=0;
    for(;p>0;p&=p-1)
        res+=bits[p];
    return res;
}

int main(){
    scanf("%d", &sz);
    for(int i=1;i<=sz;i++){
        int t; scanf("%d", &t);
        mp[t]=i;
    }
    
    ll res=0;
    for(int i=1;i<=sz;i++){
        int t; scanf("%d", &t);
        int p=mp[t];
        res+=(i-1)-qry(p);
        upd(p);
    }
    printf("%lld\n", res);
}

 

여기서는 입력값의 크기가 1,000,000 이하이므로 map을 사용하지 않고 배열을 이용하는 쪽이 조금 더 빠르긴 할 것이다.

즉, 배열을 int inv[1000001]로 두고 첫 입력이 132 이면 

 

inv[132]=1;

 

같은 방식으로 처리하면 map을 사용하지 않을 수 있다.