[백준]_1461번 : 도서관(파이썬 and C언어)

1461번: 도서관

그리디 알고리즘을 사용하는 문제. 그리디 알고리즘을 사용하기 위해서는 ( 최적의 해 ) == ( 순간 최적의 해 )을 만족해야 한다. 대표적인 예시로는 충분한 수량의 500원, 100원, 50원, 10원, 1원이 있을 때 N원을 만들기 위해 조합할 수 있는 최소의 동전 수를 구하는 문제가 있다. 전략은 결국 500원이 가장 큰 비중을 차지하니까 500원으로 N원을 채우다가 500원으로 더 이상 채울 수 없으면 100원으로 옮겨가는 방법이다. 이제 이 문제가 왜 그리디 알고리즘으로 풀 수 있는 문제인지만 밝히면 된다.

---

관찰

최소 이동거리를 완성하려면 다음과 같은 특성을 이용해야 한다.

1. 0 으로 다시 돌아와야 하기 때문에 이동거리는 (목적지 * 2)이다. 단, 마지막 도서를 가지러 가는 경우는 다시 돌아올 필요가 없기 때문에 2를 곱하지 않아도 된다.
2. 양수 음수 진영에서 모두 일반적인 경우 그 진영에서 절댓값이 가장 큰 수를 찍고 돌아와야 한다. 이때 가장 큰 수를 포함한 그다음으로 절댓값이 큰 M개의 숫자를 지워준다.

따라서 원점에서 가장 멀리 있는 책을 목적지로 해야한다. 따라서 그리디 알고리즘을 사용해도 되는 문제인 것이다!!

---

시도 1(Python)

import sys
input = sys.stdin.readline

book, hold=map(int, input().split())
location=[*map(int, input().split())]
right_shelf=[]
left_shelf=[]
for num in location:
    if num>0: right_shelf.append(num)
    else: left_shelf.append(num)
right_shelf.sort()
left_shelf.sort(reverse=True)
move=0
last_location='n'
if len(right_shelf) > 0 and (len(left_shelf) == 0 or right_shelf[-1] > abs(left_shelf[-1])):
    last_location = 'p'

if last_location=='p':
    move+=right_shelf[-1]
    del right_shelf[-hold:]
elif last_location=='n':
    move+=abs(left_shelf[-1])
    del left_shelf[-hold:]
while len(right_shelf)+len(left_shelf)!=0:
    if len(right_shelf):
        move+= right_shelf[-1] * 2
        del right_shelf[-hold:]
    if len(left_shelf):
        move += abs(left_shelf[-1]) * 2
        del left_shelf[-hold:]
print(move)

 

시도 2(C언어)

#include <stdio.h>
#include <stdlib.h>
void asc_insertion_sort(int *data, int n) { //오름차순
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = data[(j = i)];
        while (--j >= 0 && key < data[j]) {
            data[j + 1] = data[j];
        }
        data[j + 1] = key;
    }
}

void re_arrange(int *data, int n) { // 특수 정렬
    int tmp;
    for (int i = 0; i < n / 2; ++i) {
        tmp = data[i];
        data[i] = data[n - i - 1];
        data[n - i - 1] = tmp;
    }
}

int main() {
    int book, hold;
    int right = 0, left = 0;

    scanf("%d %d", &book, &hold);
    // 책들의 수 만큼 배열 선언
    int *library = (int *) malloc(book * sizeof(int));
    // 도서들 위치 입력
    for (int i = 0; i < book; ++i) {
        scanf("%d", &library[i]);
        if (library[i] > 0) right++;
        else left++;
    }

    // 삽입 정렬을 이용한 배열의 정렬
    asc_insertion_sort(library, book);
    // 위에서 얻은 양수, 음수 갯수 정보를 토대로 찢어주는 작업
    int *right_shelf = (int *) malloc(right * sizeof(int));
    int *left_shelf = (int *) malloc(left * sizeof(int));
    for (int i = 0; i < left; ++i)
        left_shelf[i] = library[i];
    for (int i = left; i < right + left; ++i)
        right_shelf[i - left] = library[i];
    // 거리가 멀수록 뒤로 위치 해야 하기 때문에 left_shelf는 다시 재정렬.
    // 하지만 이미 순서가 의도의 역순이기 때문에 특수한 정렬 함수에 넣어줌으로써 최악의 시간 복잡도는 면할 수 있음.
    re_arrange(left_shelf, left);

    // 가장 멀리 있는 도서가 어디에 있는지 조사
    int move = 0;
    // p(positive), n(negative[디폴트])
    char last_location='n';
    if (right > 0 && (left == 0 || right_shelf[right - 1] > left_shelf[left - 1] * -1))
        last_location = 'p';

    // 마지막으로 도착할 위치만 먼저 빼줌
    if (last_location == 'p') {
        move += right_shelf[right - 1];
        right -= hold;
    } else {
        move += left_shelf[left - 1] * (-1);
        left -= hold;
    }

    // 계산
    while (right > 0 || left > 0) {
        if (right > 0) {
            move += right_shelf[right - 1] * 2;
            right -= hold;
        }
        if (left > 0) {
            move += left_shelf[left - 1] * (-2);
            left -= hold;
        }
    }
    printf("%d", move);
    // 메모리 풀어주기
    free(library);
    free(right_shelf);
    free(left_shelf);
    return 0;
}