[백준] #2828 사과 담기 게임

 

 

문제

 

---

Algorithm

 먼저 상자의 크기가 1일 경우를 살펴보자. 사과가 처음 떨어질 때 상자의 이동거리는 상자의 처음 위치와 사과의 위치의 차이이다. 이후로는 현재 사과의 위치와 다음 사과의 위치의 차이가 상자의 이 구간에서의 이동거리가 될 것이다. 모든 구간에서의 이동거리의 합이 답이 될 것이다.

하지만 상자의 크기가 1보다 클 경우에는 상자의 최소 이동거리를 이렇게 구할 수 없다. 먼저 상자의 좌우 각각을 기준으로 더 작은 값이 나오는 쪽을 총 이동거리에 더해간다. $t$시간에서 상자의 가장 왼쪽 부분의 위치, 가장 오른쪽 부분의 위치, 사과의 위치를 각각 $a_t,\ L_t,\ R_t$라 하자. 상자의 크기는 $M$이므로 항상 $R_t = L_t + M$의 관계가 성립한다. 상자의 처음 위치는 $L_t = 0, R_t = M$이다. 이제 $|a_t - L_t|$와 $|a_t - R_t|$를 비교하여 더 작은 쪽을 총 이동거리에 더한다. 이후 $|a_t - L_t|>|a_t - R_t|$라면 $R_{t+1}=a_t,\ L_{t+1}=a_t-M+1$으로 갱신되고 $|a_t - L_t|<|a_t - R_t|$라면 $L_{t+1}=a_t,\ R{t+1}=a_t + M-1$이다. 하지만 $L_t\leq a_{t+1}\leq R_t$인 경우에는 사과의 위치만 갱신하고 이동거리도 갱신되지 않는다.

 

---

 

 

Code

input = __import__('sys').stdin.readline

N, M = map(int, input().split())
J = int(input())

apple = []
for _ in range(J):
     apple.append(int(input()))

distance = 0
B = [1, M] # [L_t, R_t], L_1=1, R_1=M
for a in apple:
     if B[0] <= a <= B[1]:
          continue
     else:
          d1 = abs(a - B[0])
          d2 = abs(a - B[1])
     if d1 < d2:
          distance += d1
          B[0] = a
          B[1] = a + M - 1
     else:
          distance += d2
          B[0] = a - M + 1
          B[1] = a

print(distance)