[Python] 2118번 두 개의 탑

 

 

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

---

 

24/05/14

 

 

간단한 누적 합 + 두 포인터 연습문제이다.

---

 

문제 접근 방식:

 

 

두 지점을 $i$와 $j$라고 하고, 편의 상 $i \leq j$라고 가정하자.

 

원의 둘레를 $T$라고 한다면, 두 지점 사이의 거리는 다음과 같이 정의된다.

 

$$\text{min}(D[j]-D[i] , T-D[j] + D[i])$$

 

여기서 $D$는 두 지점의 위치를 나타낸다.

 

예제 입력을 통해 왜 투 포인터를 써야하는지에 대한 이야기를 해보자.

예제 입력에 대한 그림을 그리면 다음과 같다.

빨간 지점에서 시작하여 빨간 지점과 가장 멀리 떨어져 있는 곳을 반시계 방향 순으로 찾아보자.

그림을 보면 확인할 수 있듯이, 빨간 지점과 가장 멀리 떨어진 지점을 찾을 때까지 파란 지점을 뒤로 보낸다.

마치 자석의 같은 극이 서로를 밀어내는 것처럼, 빨간 지점이 고정되있다면 파란 지점을 뒤로 민다고 생각하면 된다.

 

이때, 더 이상 파란 지점을 뒤로 밀면 오히려 거리가 줄어드는 때가 있을 텐데, 그 지점이 빨간 지점과 파란 지점 사이의 최대 거리인 것이다.

 

그렇게 두 지점 사이의 최대 거리를 찾았다면, 중심이 되는 빨간 지점을 한 칸 앞으로 옮겨, 다시 최대거리를 찾으려고 한다.

그러한 최대 거리들 중에서 가장 큰 값이 여기에서 얻을 수 있는 최대 거리인 것이다.

 

둘 중 어느 한 포인터가 다시 시작지점에 온다면, 마지막 그림에서 확인할 수 있듯이, 이는 빨간 지점과 파란 지점이 뒤바뀐 경우라고 생각할 수 있다. 파란 지점에서 빨간 지점의 거리를 구하나, 빨간 지점에서 파란 지점의 거리를 구하나 같으므로, 이때 멈추면 된다.

 

문제에서는 두 지점 사이의 위치 배열을 준 것이 아니라 두 지점 사이의 거리 배열을 주었다.

누적 합을 사용하면 이 배열을 위치배열로 쉽게 바꿀 수 있다.

---

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

# 2118번 두 개의 탑
# 두 포인터, 누적 합
'''
접근 방법:
두 지점을 i, j라고 한다면, 두 지점 사이의 거리는 다음과 같다.
전체 거리를 T라고 하면,
dis = min(D[j] - D[i], T - D[j] + D[i])
이 거리가 최대가 되도록 포인터를 움직여가며 구해준다.
'''
import sys
input = sys.stdin.readline
from itertools import accumulate

N = int(input())
D = [0] + list(accumulate(int(input()) for _ in range(N)))
T = D[-1]
start, end = 0, 0
max_dis = 0
while start < N and end < N:
    dis = min(D[end]-D[start], T-D[end]+D[start])
    if dis > max_dis:
        max_dis = dis
    if D[end]-D[start] < T-D[end]+D[start]:
        end += 1
    else:
        start += 1
print(max_dis)