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

도서관에 책 갖다놓아야하는데 책의 위치는 직선상에 있으나 위치가 -10000부터 10000사이에 있다. 이 때 책을 한 번에 m권을 들 수 있을 때 책을 갖다놓는 거리가 가장 짧을 때의 거리를 찾는 문제이다.

처음에 어떻게 접근할 지 몰라서 힌트를 봤더니 DP를 사용하라고 했다.

그래서 0을 기준으로 음의 위치와 양의 위치에 있는 책을 나누고 각자 절댓값 오름차순으로 정렬했다.

그리고 다음 점화식을 만들었다.

dp[n] = books[n] + min(dp[n-m] + books[n-m], dp[n-m+1] + books[n-m+1], ... ,dp[n-1] + books[n-1]) 

n-m번째 책까지 가져다 놓고, n-m-1부터 n까지 m권의 책 한 번에 가져가기,
n-m+1번째 책까지 가져다 놓고, n-m부터 n까지 m-1권의 책 한 번에 가져가기,
...
n-1번째 책까지 가져다 놓고, n번째 책 가져가기

양의 위치에 있는 책과 음의 위치에 있는 책을 pb, nb로 정리한 다음 점화식을 바탕으로 코드를 작성했다.

Python

n, m = map(int, input().split())

pb = []
nb = []

for b in map(int, input().split()):
  if b < 0:
    nb.append(-b)
  else:
    pb.append(b)
    
nb.sort()
pb.sort()
dp = [-1] * len(nb)

i = 0
while i < m and i < len(nb):
  dp[i] = nb[i]
  i+=1

ans = 0
for i in range(m, len(dp)):
  dp[i] = dp[i-m] + nb[i-m] + nb[i]
  
  b = m-1
  while b >= 1:
    dp[i] = min(dp[i], dp[i-b] + nb[i-b] + nb[i])
    b-=1
if dp:
  ans += dp[-1]


dp = [-1] * len(pb)
i = 0
while i < m and i < len(pb):
  dp[i] = pb[i]
  i+=1

for i in range(m, len(dp)):
  dp[i] = dp[i-m] + pb[i-m] + pb[i]
  b = m-1
  while b >= 1:
    dp[i] = min(dp[i], dp[i-b] + pb[i-b] + pb[i])
    b-=1
if dp:
  ans += dp[-1]

print(ans + min(pb[-1] if pb else 0, nb[-1] if nb else 0))

nb, pb 모두 m권까지는 한 번에 가져가는게 더 효율적이므로 그대로 값을 복사했다.

그리고 각각 점화식의 내용을 수행하고 나서 ans에 dp의 최종값을 더해주었다.

모든 연산이 끝나면 두 dp 모두 현재 위치가 nb[-1]과 pb[-1]에 있기 때문에 한 번은 0으로 와서 반대편으로 가야한다.
그래서 음의 끝과 양의 끝 중 더 가까운 곳을 ans에 더해주는데 이 때 pb나 nb의 길이가 0이라면 마지막에 0으로 돌아올 필요가 없기 때문에

else 0

을 해주었다.

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] line = scanner.nextLine().split(" ");

        int n = Integer.parseInt(line[0]), m = Integer.parseInt(line[1]);
        line = scanner.nextLine().split(" ");

        ArrayList<Integer> pb = new ArrayList<>();
        ArrayList<Integer> nb = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (Integer.parseInt(line[i]) > 0) {
                pb.add(Integer.parseInt(line[i]));
            } else {
                nb.add(-Integer.parseInt(line[i]));
            }
        }

        Collections.sort(pb);
        Collections.sort(nb);

        int ans = 0;
        int[] dp = new int[pb.size()];

        for (int i = 0; i < m; i++) {
            if (i == pb.size()) {
                break;
            }
            dp[i] = pb.get(i);
        }

        for (int i = m; i < dp.length; i++) {
            dp[i] = pb.get(i) + dp[i - m] + pb.get(i - m);
            for (int b = m - 1; b >= 1; b--) {
                dp[i] = Math.min(dp[i], dp[i - b] + pb.get(i - b) + pb.get(i));
            }
        }

        if (dp.length > 0) {
            ans += dp[dp.length - 1];
        }

        dp = new int[nb.size()];
        for (int i = 0; i < m; i++) {
            if (i == nb.size()) {
                break;
            }
            dp[i] = nb.get(i);
        }

        for (int i = m; i < dp.length; i++) {
            dp[i] = nb.get(i) + dp[i - m] + nb.get(i - m);
            for (int b = m - 1; b >= 1; b--) {
                dp[i] = Math.min(dp[i], dp[i - b] + nb.get(i - b) + nb.get(i));
            }
        }

        if (dp.length > 0) {
            ans += dp[dp.length - 1];
        }

        System.out.println(ans + Math.min(!pb.isEmpty() ? pb.get(pb.size() - 1) : 0, !nb.isEmpty() ? nb.get(nb.size() - 1) : 0));

        scanner.close();

    }
}