[Python] 백준 2118 - 두 개의 탑 문제 풀이

Overview

BOJ 2118번 두 개의 탑 문제 Python 풀이
분류: 투포인터(Two Pointer), 누적합 (Prefix Sum)

---

문제 페이지

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

---

풀이 코드

from sys import stdin
input = lambda: stdin.readline().rstrip()


if __name__ == "__main__":
    N = int(input())
    dists = [int(input()) for _ in range(N)]

    # 거리 리스트 두 개를 이어 붙인 리스트의 prefix sum
    ps = [0] * (2 * N + 1)
    for i in range(2 * N):
        ps[i + 1] = ps[i] + dists[i % N]

    ans = 0
    total, right = sum(dists), 1
    for left in range(2 * N):
        # 시계 방향 거리가 반시계 방향 거리보다 크면 거리를 줄임
        while right < 2 * N + 1 and ps[right] - ps[left] <= total - ps[right] + ps[left]:
            ans = max(ans, ps[right] - ps[left])
            right += 1
    print(ans)

투포인터와 누적합을 응용한 풀이이다. 거리가 저장된 dists 리스트를 복사하여 뒤에 붙여 길이가 2N인 리스트를 만든다. 그리고 해당 리스트의 누적합을 구한 뒤, 투포인터를 이용해 두 점 사이의 거리를 탐색한다.