[백준] No.7578 - 공장 (C++, Inversion Counting)

문제

 

https://www.acmicpc.net/problem/7578

7578번: 공장

 

 

풀이

 

solved.ac 난이도: Platium 5

 

 Inversion Counting 문제를 세그먼트 트리를 이용해 해결하는 문제.

 

해결법은 다음과 같다.

 

한 기계의 쌍의 A라인의 위치를 a_idx, B라인에서의 위치를 b_idx라고하자.

이 기계의 케이블과 교차되기 위해서는 해당 기계의 A라인에서의 위치(a_new)가 a_idx보다 앞에 있고

B라인에서의 위치(b_new)가 b_idx보다 뒤에 있어야 한다.

a_new < a_idx && b_idx < b_new

 

 

위의 기계 배열에서는 100번 기계와 교차되는 기계들은 300번과 400번 기계이다.

100번과 교차하기 위해서는 A라인에서 위치는  4보다 작고 B라인에서는 2보다 커야 한다

300과 400 두 기계 모두 a_new < a_idx && b_idx < b_new 가 성립한다.

 

하지만 100번과 겹치지 않는 200번 기계는 A라인에서는 4보단 작은 3에 위치하지만

B라인에서는 2보다 작은 1에 위치하기 때문에 교차하지 않는다. 

 

이런 식으로 교차하는 기계들의 위치를 확인할 때, A라인 위치를 기준으로 삼고 앞의 위치(작은 위치)부터 뒤로 순서대로 교차를 확인한다고 생각해보자.

이런 경우 현재 기계(machine)에 도달했다면 machine의 A위치 보다 앞에 있는 기계들은 이미 확인을 끝내고 오게 된다.

즉 앞의 기계들은 a_new<a_idx 조건인,  A라인의 위치보다는 작아야 한다는 조건은 만족하게 된다.

따라서 우리는 앞의 기계들 중에 B라인에서 위치가 machine보다 큰 것을 찾으면 된다.

 

이를 구현하기 위해 세그먼트 트리가 사용된다.

 

일단 방문 여부를 확인하기 위해 모든 노드의 값은 0으로 초기화해준다.

이제 A라인에 배치된 순서대로 기계의 케이블 교차 여부를 확인한다.

이때 이미 방문한 기계는 +1로 값을 업데이트해준다.

 

 

400번 기계는 B라인에서의 위치 4보다 큰 위치의 방문한 기계가 없다.

따라서 교차점은 0개이다.

 

 

 

300번 기계의 경우, B라인의 3보다 큰 구간 [4,4]에서 방문한 값이 1개 존재한다.

따라서 300번 기계 케이블의 교차점은 1개이다.

 

 

200번 기계에서 B라인 위치보다 큰  구간 [2,4]에서 방문한 값은 2개이다.

따라서 200번의 교차점은 2개이다.

 

 

 

마지막으로 100번의 B라인 조건 구간은 [3,4]이고

조건에 해당하는 교차점은 2개이다.

 

 

최종적으로 각 기계들의 모든 교차점의 합이 정답이 된다.

(방문순서대로) 0 + 1 + 2 + 2 = 5

 

이와 같은 구현을 위해 방문한 기계의 표현은 특정 원소를 포함하는 모든 구간을 변경해주는 Update함수를,

B라인에서의 조건 구간에서의 방문한 기계를 세는 함수는 Sum함수로 구현해준다.

 

 

 

코드