https://www.acmicpc.net/problem/2118
2118번: 두 개의 탑
첫째 줄에 지점의 개수 N(2 ≤ N ≤ 50,000)이 주어진다. 다음 N개의 줄에는 차례로 두 지점 사이의 거리가 양의 정수로 주어진다. 전체 거리의 총 합은 1,000,000,000을 넘지 않는다.
www.acmicpc.net
투포인터 문제다.
풀이
문제에 주어지는 두 지점사이의 거리는 시계방향과 반시계 방향 중 짧은 쪽이 거리가 된다고 한다. 즉 시계방향 기준 반시계 방향 거리라 함은 (전체 길이 - 시계방향 거리) 로 계산이 가능하며 해당 지점의 거리는 둘 중 적은 거리로 정해진다는 것이다.
시작 인덱스와 끝 인덱스를 생성하여 구간의 길이를 측정한다. 구간의 길이가 최대거리보다 짧거나 같다면, 끝 인덱스를 한칸 늘린다. 반대로 현재 구간의 길이가 최대값보다 크다면, 시작 인덱스를 증가한다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [22862] 가장 긴 짝수 연속한 부분 수열 (large) (0) | 2023.01.19 |
|---|---|
| [1484] 다이어트 (0) | 2023.01.18 |
| [1652] 누울 자리를 찾아라 (0) | 2023.01.16 |
| [15565] 귀여운 라이언 (0) | 2023.01.15 |
| [1337] 올바른 배열 (0) | 2023.01.14 |