[c++] 백준 #14458 소가 길을 건너 간 이유 10

< 풀이 >

교차점을 세는 방식이 생각하기 어려운 문제였다.

회전 시 생기는 교차의 수를 매번 새로 세줘야 하는데 naive 하게 구현하면 당연히 O(N^3)이라 시간 초과.

한 번 회전할 때마다 나름의 규칙성을 찾아보면,

회전 시 교차점의 수는 이전 교차의 수 – 현재 간선으로 생긴 교차의 수 + 새로 생기는 교차의 수가 된다.

이전 교차의 수는 회전할 노드보다 right가 더 큰 노드의 개수 (코드에서 N-right_idx[left_rev[i])

새로 생기는 교차의 수는 회전할 노드보다 right가 작은 노드의 개수. (코드에서 right_idx[left_rev[i])

이렇게 대략적으로 회전 시 교차선 수 개수 변화를 구할 수가 있는데, 관건은 맨 처음 상태에서 교차점 개수를 계산하는 것이다. 여기에서 펜윅트리를 사용하는 아이디어를 얻는다고 한다.(ㅠㅠ) 

일단 교차가 어떻게 생기는지 보면,

나보다 left가 위에 있는 노드가 나보다 right가 아래에 있거나, 나보다 left가 아래에 있는 노드가 나보다 right가 위에 있으면 생기게 된다. 두 경우 중 하나만 따져줘도 되는데, left와 right 조건이 동시에 움직이면 어려우니까 맨 아래부터 간선을 추가하는 식으로 생각해보자.

그러면 left 값은 고정이니까 맨 뒷 노드부터 간선을 하나씩 추가하면, 현재 추가하려는 간선의 right 값보다 더 작은 값의 갯수(1~right-1까지 중에서) = 나보다 아래에 있는 노드 중 right가 나보다 작은 노드의 개수가 되므로 1부터 right 이전의 부분합을 빠르게 계산하기 위해 펜윅트리를 쓴다고 보면 되겠다.

 

** 구현 시 주의해야 할 점

1) left와 right가 둘 다 회전할 수 있다. left가 회전할 때와 right 가 회전할 때 값이 다른 반례를 하나 적당히 찾아보면 이런 게 있다.

6   
1 6 5 2 4 3
1 2 3 4 5 6

2) 최악의 경우 매 순간순간마다 이전 노드의 개수만큼 간선이 생길 수 있다.

1+2+...+(n-1) = n(n+1)/2 이므로 n=10만이면 연결 선의 개수는 최대 50억까지 갈 수 있다. int 대신 long long을 사용해주어야 한다.

 

< 소스코드 >

#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long ll;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

#define N_MAX 100010

ll left_rev[N_MAX]; // left_rev[i] = v : left에서 i번째 위치에 있는 node의 번호는 v
ll right_rev[N_MAX]; 
ll left_idx[N_MAX]; // left_idx[v] = i : left에서 노드 v가 있는 위치는 i
ll right_idx[N_MAX];
ll tree[N_MAX]; // fenwick tree

ll N, n_connections;
ll ans;


ll sum(ll idx){
    ll ans = 0;
    while (idx > 0){
        ans += tree[idx];
        idx -= idx & (-idx); // 가장 낮은 bit부터 하나씩 끈다
    }
    return ans;
}

void update(ll idx, ll value){
    while(idx <= N){
        tree[idx] += value;
        idx += idx & (-idx); // 가장 낮은 bit부터 하나씩 값을 더한다
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    for(int i=1; i<=N;i++){
        int v; cin >> v;
        left_idx[v] = i;
        left_rev[i] = v;
    }
    // 1부터 N까지의 값
    for(int i=1; i<=N;i++){
        int v; cin >> v;
        right_idx[v] = i;
        right_rev[i] = v; 
    }

    // 1~cur_v까지 갯수 세기 : 펜윅트리 with N개 노드
    // 펜윅 트리를 이용해서 맨 처음에 전체 교차점의 갯수를 구한다
    // 맨 뒤의 left node부터 시작해서, 노드를 하나씩 추가하면서 right가 내 앞에 있는 거 갯수를 센다. 그걸 total ans에 더해주고 자기 값도 +1
    for(int i=N; i>=1;i--){
        ll cur_v = right_idx[left_rev[i]];
        // right_idx[left_rev[i]] 앞에 노드가 몇개 있었는 지 계산해서 더한다
        n_connections += sum(cur_v);
        // right_idx[left_rev[i]] 번째 위치에서 1을 증가시킨다.
        update(cur_v, 1);
    }

    ll init_connections = n_connections;
    ans = n_connections;
    for(int i=N; i>=1; i--){
        n_connections -= (N - right_idx[left_rev[i]]); // 현재 간선으로 생긴 교차점 수는 전체 노드 - 현재 right idx
        n_connections += (right_idx[left_rev[i]]-1); // 새로 생길 교차점 수는 현재 right idx -1
        ans = min(ans, n_connections);
        cout << "n_c " << n_connections << '\n';
    }
    
    // 오른쪽을 돌려본다.
    n_connections = init_connections;
    for(int i=N; i>=1; i--){
        n_connections -= (N - left_idx[right_rev[i]]); // 현재 간선으로 생긴 교차점 수는 전체 노드 - 현재 right idx
        n_connections += (left_idx[right_rev[i]]-1); // 새로 생길 교차점 수는 현재 right idx - 1
        ans = min(ans, n_connections);
        cout << "n_c " << n_connections << '\n';
    }

    cout << ans << '\n';

    return 0;
}

 

< 풀이를 참고한 블로그 >

https://booknu.github.io/2019/04/26/BOJ14458/

백준 BOJ 14458 - [USACO Platinum] Why Did the Cow Cross the Road