[Python] 31531번 공들의 리듬게임

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

---

 

24/03/10

 

 

풀이 아이디어가 제법 알려져 있는 문제로, 이전에 비슷한 문제를 해결했다면 쉽게 해결 할 수 있는 애드혹 문제다. 

---

 

문제 접근 방식:

 

 

이 문제의 아이디어는 아래 문제에서 얻을 수 있다.

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

또는 아래 문제에서도 얻을 수 있다.

2023.09.02 - [알고리즘/백준 문제 풀이] - [Python] 13249번 공의 충돌

[Python] 13249번 공의 충돌

 

핵심 아이디어는 충돌을 통과로 생각할 수 있다는 아이디어였다.

 

이 문제도 마찬가지다. 다만 여기서는 점수를 구해야 된다.

 

정지해 있는 물체와 움직이는 물체가 충돌하는 경우에는 2점을 얻고, 움직이는 물체끼리 충돌하는 경우 1점을 얻는다고 했다.

 

주목할 점은 왼쪽, 오른쪽, 정지해 있는 공이 동시에 충돌하면 5점을 얻는다고 한 점이다.

 

왼쪽, 오른쪽, 정지해 있는 공이 동시에 충돌하는 경우는 정지해 있는 물체와 움직이는 물체가 충돌하는 경우가 두 번, 움직이는 물체끼리 충돌하는 경우가 한 번으로 분리할 수 있으며, 실제로도 점수가 $2+2+1=5$점으로 나오기 때문에 그렇게 계산해도 된다.

 

따라서, 실제로 움직이는 상황을 구현하지 않아도 정지해 있는 물체와 움직이는 물체가 충돌하는 경우와, 움직이는 물체끼리 충돌하는 경우를 세어서 그 충돌 횟수만 잘 세어주면 점수를 계산할 수 있다.

 

예제 입력들에 대한 그림은 문제에 나와 있으니 이를 잘 참고해보자.

 

예제 입력 4에 대한 그림은 다음과 같다.

예제 입력 4

맨 처음 4의 위치에 있던 오른쪽 방향으로 움직이는 공의 입장에서 보았을 때에는 5번 위치에 있던 공, 6번 위치에 있던 공, 8번 위치에 있던 공을 통과하여(실제로는 충돌하여 다른 공이지만) 점수를 획득한 것으로 간주할 수 있다.

 

이때, 8번 위치의 공은 움직이는 공이므로 1점, 5번 위치와 6번 위치의 공은 정지해 있는 공이므로 각각 2점씩 획득하여, 총 5점을 얻을 수 있다.

 

마찬가지로, 8의 위치에 있던 왼쪽 방향으로 움직이는 공의 입장에서 보았을 때에는 6번 위치에 있던 공, 5번 위치에 있던 공, 4번 위치에 있던 공을 통과하여(실제로는 충돌하여 다른 공이지만) 점수를 획득한 것으로 간주할 수 있다.

 

이때, 5번 위치와 6번 위치의 공은 정지해 있는 공이므로 각각 2점씩 획득, 4번 위치의 공은 움직이는 공인데, 이전에 점수를 세었으므로, 이를 모두 더하면 9점을 얻을 수 있다.

 

 

이 점수들은 다음과 같은 방법으로 카운팅해주었다.

 

1. 먼저, 오른쪽으로 움직이는 공과 왼쪽으로 움직이는 공, 정지해 있는 공의 좌표를 각각 따로 따로 저장해서 배열에 담아준다.

이 배열들의 이름을 각각 right, left, mid라고 이름 붙였다.

 

2. 이후, mid와 left를 정렬하였다. 이는 이분 탐색을 활용하여 시간을 줄이기 위함이다.

 

3. 위에서 했던 것과 동일한 방법으로, right의 각 원소마다 mid의 원소를 몇 개 지나는지 카운팅 해주었다.

이때, 이전에 mid배열을 정렬했기 때문에 right의 각 원소(좌표)가 mid배열 어디에 위치해 있을 지를 이분 탐색을 통해 쉽게 파악할 수 있으므로, 오른쪽으로 움직이는 공이 정지해 있는 공 몇 개를 지나는 지를 빠르게 파악할 수 있다.

mid배열의 크기를 $M$, right배열의 크기를 $R$이라고 한다면, 시간 복잡도는 $\mathcal{O}(R \log M)$이다.

 

4. 마찬가지로, left의 각 원소마다 mid의 원소를 몇 개 지나는지를 카운팅 해주었다.

이분 탐색을 활용하여 빠르게 판단할 수 있으며, left배열의 크기를 $L$이라고 한다면, 시간 복잡도는 $\mathcal{O}(L \log M)$이다.

 

5. 3번과 4번에서 구한 카운팅 개수에 $2$를 곱한 것이 정지해 있는 공과 움직이는 공이 충돌할 경우에 얻을 수 있는 점수이다.

 

6. right의 각 원소마다 left의 원소를 몇 개 지나는지 카운팅 해준다. 이는 오른쪽으로 움직이는 공과 왼쪽으로 움직이는 공이 충돌하는 경우의 점수에 해당한다.

left배열이 정렬되어 있기 때문에 이분 탐색을 활용하여 시간을 줄일 수 있으며, 시간 복잡도는 $\mathcal{O}(R \log L)$이다.

 

7. 따라서 총 시간 복잡도 $\mathcal{O}(N \log N)$으로 문제를 해결할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 공들의 리듬게임
# subtask-4
import sys
input = sys.stdin.readline
from bisect import bisect_left

N = int(input())
left = []
right = []
mid = []
for _ in range(N):
    n, d = map(int, input().split())
    if d == 1:
        right.append(n)
    elif d == -1:
        left.append(n)
    else:
        mid.append(n)
left.sort()
mid.sort()
count = 0
for i in range(len(right)):
    count += 2*(len(mid) - bisect_left(mid, right[i]))
for i in range(len(left)):
    count += 2*bisect_left(mid, left[i])
for i in range(len(right)):
    count += (len(left) - bisect_left(left, right[i]))
print(count)