Hyun's_Devlog

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

세그먼트 트리 문제다.

풀이

A열의 좌측부터 연결해 가면서 계산이 이루어져야 한다. 각 A열의 기계번호가 B열에서 몇 번째에 위치한 지 찾아낸 뒤, 해당 위치부터 N-1번째 까지 몇 개의 기계가 연결되어 있는지 개수를 저장하면 된다. 구간 합 세그먼트트리와 딕셔너리를 이용하여 접근하였다.

예제를 기준으로 설명하면 다음과 같다.

A열의 0번 기계는 B열의 2번에 위치해 있다. 0~4까지의 연결된 기계의 개수를 조회한다.

구간에 연결된 기계가 하나도 없으므로 +0.

다음으로 A열 1번 기계는 B열의 0번에 위치한다. 0~4구간의 연결된 기계의 개수 조회.

한 개(2번)가 있으므로 +1.

A열 2번은 B열의 3번에 위치. 3~4구간 조회.

하나도 없으므로 +0.

A열 4번은 B열의 1번에 위치하여 1~4구간 조회.

두 개(2번, 3번)가 있으므로 +2.

마지막으로 A열 4번은 B열의 4번에 위치.

마지막 인덱스이므로 뒤에 연결된 기계가 없다. 즉 정답은 3을 출력한다.

정답 코드