https://www.acmicpc.net/problem/1461
효율적인 동선을 짜는 문제인데, 들고 다닐 수 있는 책의 개수가 한정되어 있다.
모든 책이 0위치에 있기 때문에 들고 있는 책 정리를 끝냈다면 다시 0으로 돌아와야 한다.
어차피 돌아와야 한다면 책을 정리하러 갔다가 오는 동선에 다른 책들을 정리하면 효율적인 동선이 된다.
따라서 제일 먼 거리를 갔다가 오면서 들고 있는 책들을 정리하게 된다.
책의 위치가 음수일 수도 있으므로 책의 위치를 양수와 음수로 나누어 따로 정리하면 동선을 더 줄일 수 있다.
책들을 오름차순으로 정리한 다음, 양수 위치의 책들을 M개씩 정리하면서 제일 먼 거리 * 2만큼 이동 거리에 누적한다.
음수 위치의 책들도 마찬가지이다.
그런데 모든 책의 정리를 끝냈다면 0으로 돌아오지 않는다고 하니, 마지막 동선이 제일 먼 거리의 책이라면 편도로만 가면 되기 때문에 이 점을 생각해야한다.
앞서 이동 거리를 누적시킬 때 제일 먼 거리가 왕복으로 계산되었기 때문에 이동 거리에서 제일 먼 거리를 빼주면 편도로 간 셈이 된다.
#include <iostream>
#define ABS(X) ((X) > 0 ? (X) : -(X))
int main() {
int N, M, arr[50]{0}, positiveStartIndex = 0;
scanf("%d %d", &N, &M);
for (int i = 0; i < N; i++) {
scanf("%d", &arr[i]);
if (arr[i] < 0) {
positiveStartIndex++;
}
}
for (int i = 0; i < N - 1; i++) {
for (int j = i + 1; j < N; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
int dist = 0;
for (int i = N - 1; i >= positiveStartIndex; i -= M)
dist += arr[i] * 2;
for (int i = 0; i < positiveStartIndex; i += M)
dist += ABS(arr[i]) * 2;
int max = 0;
for (int i = 0; i < N; i++) {
max = ABS(arr[i]) > max ? ABS(arr[i]) : max;
}
dist -= max;
printf("%d", dist);
}
'프로그래밍 > 알고리즘' 카테고리의 다른 글
16931 겉넓이 구하기 (0) | 2022.09.01 |
---|---|
1485 정사각형 (0) | 2022.08.31 |
2232 지뢰 (0) | 2022.08.29 |
2226 이진수 (0) | 2022.08.29 |
1262 알파벳 다이아몬드 (0) | 2022.08.20 |
댓글