백준[17671] 로봇 (Python3)

다3 치고 생각보다 풀만했던 문제.
관찰을 하면서 탐색 범위를 조금씩 좁혀나간다면 충분히 해결할 수 있다.

랑이집사님이 알려주신 완전 탐색부터 시작하는 최적화를 잘 써먹은 문제

완전 탐색

로봇의 움직임을 3가지를 나눠 계산한다.
1. 왼쪽으로 한 칸 갈 때
2. 가만히 있을 때
3. 오른쪽으로 한 칸 갈 때

이 방법으로 문제를 해결할 경우 O(3^N)으로 시간 초과가 난다.

이를 줄이기 위해, 로봇이 움직이는 거리를 높이거나, 일부 로봇은 움직이지 않는 식으로 탐색 범위를 좁혀나가야 한다 생각했다.

 

완전탐색 최적화 1

처음부터 로봇을 최소한만 겹칠 수 있게 이동
겹치게 된다면 안 겹치도록 입력된 위치에서 + 를 해준다.
하지만, 이 방법은 로봇들이 서로 가까이에 있다면, 불필요하게 많이 이동하는 경우가 생긴다

 

완전탐색 최적화 2

두 로봇 간 겹치는 범위를 최소한으로 조정
로봇끼리 감시 범위가 겹친다면 번호가 작은 로봇을 왼쪽으로 이동, 간격이 있다면 오른쪽으로 이동.
마지막 번호의 로봇은 첫번째 로봇과 비교한다.
이 방법의 경우 예제 2가 반례가 됐다.

 

완전탐색 최적화 3

M의 범위가 큰 것을 이용해 이분 탐색 사용.
구해진 중간 값 이내로 감시 범위가 겹치는 로봇들을 시계 방향으로 이동시키며 감시 범위의 시작점, 끝점을 갱신.
마지막 로봇의 감시 범위와 첫번째 로봇의 감시 범위가 겹치는지를 본다.
O(log2RN * N)으로 풀 수 있을 거 같은데 감시 범위가 0을 넘는 경우에 대한 분기처리가 복잡해져서 다른 방법을 생각했다.

완전탐색 최적화 4

이분탐색 시도를 통해 로봇을 한 쪽으로만 이동시키면 문제를 해결 할 수 있다고 생각했다.
따라서 로봇이 시계 방향으로 가는 것만 생각했다.

먼저 각 로봇들의 간격을 구한다. 이 때, 감시 범위 * 2 만큼 빼야 한다. 
빼는 이유는 로봇의 감시 범위가 2이고, 위치가 각각 0, 6일 때, 각 로봇은 서로의 방향으로 1칸씩만 가주면 되기 때문이다.

여기서 실수할 수 있는게, 순환 구조이기 때문에, 첫 번째 로봇이 아닌, 다른 로봇을 기준으로 이동시키는게 정답인 경우가 있다.
따라서, 기존에 구한 간격 배열을 하나 더 복사해 이어붙인다.

이제, 로봇간 간격을 더해나간다. 즉, 누적합을 사용한다.
다만, 우리는 시계 방향으로 가는 것만 고려하니, 간격이 음수이면 누적합을 중단하고 양수가 나오면 거기서 다시 더해나간다.
이 과정에서 간격 누적합의 최대값을 구한뒤, (최대값 + 1) / 2를 해준다.

+1을 하는 이유는 간격이 홀수라면, 한 로봇은 한 칸을 더 가야 하기 때문이고
/2를 하는 이유는 위에서 말했듯이, 두 로봇이 서로의 방향으로 이동하면 최대 이동 거리를 줄일 수 있기 때문이다.

 

코드

N = int(input())
R, M = map(int, input().split())
robots = list(map(int, input().split()))
robots.sort()
R *= 2
distance = []
for i in range(N - 1):
    distance.append(robots[i + 1] - robots[i] - R)
distance.append((robots[0] - robots[-1]) % M - R)
temp = distance[:-1]
for t in temp:
    distance.append(t)
ans = 0
for i in range(1, len(distance)):
    if distance[i - 1] > 0:
        distance[i] += distance[i - 1]
    ans = max(ans, distance[i])
print((ans + 1) // 2)