[python] 백준 14463번 : 소가 길을 건너간 이유9

 

 

 

링크: https://www.acmicpc.net/problem/14463

난이도: P4

---

문제

---

이것은 존이 농장을 개편하기 전의 이야기이다.

존의 농장에는 원형 목초지가 있고, 그 둘레에 길이 둘러져 있다. 존의 소는 매일 아침 이 길을 건너가 풀을 먹고 저녁에 다시 길을 건너가 헛간으로 돌아간다.

이 소들은 자신의 습관대로 매일 똑같은 방법으로 길을 건넌다. 각각의 소는 원형 길의 정해진 한 점을 지나 들어오고, 다른 점을 지나 나간다. 어떤 두 소도 길 위의 같은 점을 지나가지 않는다. 이걸 지켜본 존은 이 점들을 분석해 보기로 했다. 소는 총 N마리고, 1, 2, ..., N이라는 번호가 붙는다. (원래 A부터 Z까지 이름이 있었는데, 소가 많아지면서 더 이상 그 방법을 사용할 수 없게 되었다.) 존은 2N개의 점을 시계방향으로 보면서 각 점을 어떤 소가 지나가는지 기록했다. 이렇게 만들어 낸 길이 2N의 수열에는 각 번호가 두 번씩 나타날 것이다.

어떤 두 소는 어떤 방법으로 걷든 그 경로가 어딘가에서 만나야 될 수도 있다. 그런 소가 총 몇 쌍인지 구해 보자.

 

입력

---

첫 줄에 N (1 ≤ N ≤ 50,000)이 주어진다. 다음 2N줄에는 한 줄에 하나씩 길 위의 점을 지나간 소의 번호가 주어진다.

 

출력

---

경로가 무조건 만나는 소가 몇 쌍인지 출력한다.

 

예제 입력

4
3
2
4
4
1
3
2
1

예제 출력

3

풀이

---

세그먼트 트리의 구간합을 이용한 문제이다.

 

풀이 개념은 아래와 같다.

각 소들이 이동한 점을 선분으로 그었을 때, 점접의 갯수가 정답이 된다.

그렇다면, 시작점(x)을 i번째 소가 처음 들어간 점. 끝점(y)을 i번째 소가 나온 점 이라고 하고(x<y), 시작점이 x보다 낮은 소의 끝점을 z라 할때 x<z<y을 만족하면 두 소는 접점을 이루게 된다.

그렇다면 소들을 시작점 기준으로 정렬하고(시작점 기준으로 정렬하면 i+1번째 소는 1~i번째 소의 시작점들보다 앞에 있으므로 끝점만 고려하면 된다.) 정렬 순서대로 x,y사이에 다른 도착점의 갯수들을 구해 결과값에 더해주고 구간합 세그먼트 트리의 인덱스y에 1을 넣어주는 것을 반복하면 정답이 나온다.

 

 

※ 주의사항

제출코드

import sys
input=sys.stdin.readline

N=int(input())
li=[[] for _ in range(N)]
M=N*2
tree=[0]*(M*4)
res=0
def update(le,ri,node,idx):
    if idx<le or ri<idx:
        return 0
    if le==ri==idx:
        tree[node]=1
        return
    mid=(le+ri)//2
    update(le,mid,node*2,idx)
    update(mid+1,ri,node*2+1,idx)
    tree[node]=tree[node*2]+tree[node*2+1]
def query(st,end,node,le,ri):
    if end<le or ri<st:
        return 0
    if st<=le and ri<=end:
        return tree[node]
    mid=(le+ri)//2
    return query(st,end,node*2,le,mid)+query(st,end,node*2+1,mid+1,ri)

for i in range(M):
    now=int(input())
    li[now-1].append(i+1)
li.sort(key=lambda x:x[0])

for x,y in li:
    res+=query(x,y,1,0,M-1)
    update(0,M-1,1,y)
print(res)

 

---

틀린 부분이 있거나 인용한 부분에 대해 문제가 있을 시
댓글로 알려주시면 감사하겠습니다.