[백준/2184] 김치 배달 (Python)

Problem : https://www.acmicpc.net/problem/2184

2184번: 김치 배달

 

Difficulty : Platinum 3

 

Status : Solved

 

Time : 00:33:08

 

---

 

문제 설명

 

 

월드 식품에서는 김치를 만들어 여러 도시들에 배달 판매하는 일을 하고 있다. 각각의 도시들과 김치 공장은 1차원 직선상의 점에 위치해 있다. 각 도시는 정수 좌표로 나타난다.

배달을 할 때에는 공장에서 N(1 ≤ N ≤ 1,000)포기의 김치를 들고 시작한다. 그리고 1차원 직선을 따라 왼쪽이나 오른쪽으로 움직인다. 이동을 할 때에는 1초에 한 칸씩 움직일 수 있다. 또한 어떤 도시에 도착했을 때 김치는 0의 시간에 배달되는 것으로 생각한다. 즉 도시에 도착하기만 하면 배달이 완료되는 것으로 생각한다. 또한 김치를 배달하는 순서는 상관이 없다.

각각의 김치는 모두 t = 0 의 시각에 공장에서 출발된다. 각각의 김치는 1초에 1만큼씩 쉬게 되는데, 김치가 쉬게 될 경우 소비자가 불만을 토로할 수 있다. 따라서 월드 식품에서는 각 도시에 김치가 도착했을 때의 김치의 쉰 정도의 합을 최소로 하려 한다.

각 도시의 위치 및 김치 공장의 위치(x좌표)가 주어졌을 때, 모든 도시에 김치를 배달할 때의 김치의 쉰 정도의 합의 최솟값을 구하는 프로그램을 작성하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에 두 정수 N, L이 주어진다. L은 김치 공장의 x좌표이다. 다음 N개의 줄에는 김치를 배달할 도시의 x좌표가 주어진다. 모든 좌표는 1이상 1,000,000이하의 정수이다.

 

출력

 

첫째 줄에 답을 출력한다.

 

입력 예시

 

4 10
1
9
11
19

 

출력 예시

 

44

 

 

---

 

풀이

 

DP로 접근해보자.

 

• 어떤 지역에 김치 배달을 진행한다고 가정했을때, 우리는 손쉽게 그 지역의 최인접 좌측, 혹은 우측에 배달하는 경우가 제일 효율적임을 알 수 있다.
• 즉 초기 지역을 중심으로 좌측, 우측으로 구분하고, 좌측 i번째, 우측 j번째를 배달한 경우를 상정하자.
  • 현재 위치는 좌측 i번째, 혹은 우측 j번째 위치일 수 있다. 이 경우를 k로 규정하자(k = 0이면 좌측에 위치, k = 1이면 우측에 위치) 
  • 이때, 좌측으로 i+1번째, 우측으로 j+1번째로 배달이 가능하다.
  • 또한, 소요 거리는 현재 위치와 이동하고자 하는 위치간의 차가 된다. 이 거리를 dist라고 하자.
  • 이 소요 거리 동안, 남은 김치들이 동시에 쉬게 된다. 남은 김치의 수가 N개라면, 총 N*dist만큼 김치가 쉬게 된다.
  • 총 김치의 쉰 정도의 합을 최소화하도록 DP를 사용하자.
• 이렇게 문제를 풀 경우, 총 시간복잡도는 O(N^2)이 된다.

 

 

풀이 코드

import sys
input = sys.stdin.readline
N, L = map(int, input().split())
kimchi = [int(input()) for _ in range(N)]
left = sorted([k for k in kimchi if k < L], reverse = True)
right = sorted([k for k in kimchi if k >= L])
MAX = float('inf')
dp = [[[MAX]*2 for _ in range(len(right)+1)] for _ in range(len(left)+1)]
if left :
  dp[1][0][0] = abs(L-left[0])*N
if right :
  dp[0][1][1] = abs(L-right[0])*N

for i in range(1, N) :
  for j in range(i+1) :
    l, r = j, i-j
    for k in range(2) :
      if l > len(left) or r > len(right) or dp[l][r][k] == MAX :
        continue
      if l+1 <= len(left) :
        if k == 0 and l > 0 :
          dist = abs(left[l] - left[l-1])
        elif k == 1 and r > 0 : 
          dist = abs(left[l] - right[r-1])
        else :
          dist = MAX
        dp[l+1][r][0] = min(dp[l+1][r][0], dp[l][r][k] + (N-i)*dist)
      if r+1 <= len(right) :
        if k == 0 and l > 0 :
          dist = abs(right[r] - left[l-1]) 
        elif k == 1 and r > 0 : 
          dist = abs(right[r] - right[r-1])
        else :
          dist = MAX
        dp[l][r+1][1] = min(dp[l][r+1][1], dp[l][r][k] + (N-i)*dist)
print(min(dp[-1][-1]))

풀이 완료!