알고리즘 - Python / 백준 - 1461번 : 도서관

1461번: 도서관 (acmicpc.net)

1461번: 도서관

 

---

풀이

• 수직선 상의 좌표에 책을 가져다 두어야 하고 , 한 번에 m개의 책을 들 수 있다.
• 이때 가장 적게 움직이면서 책을 가져다 두려면 얼마나 움직여야 하는지 구하는 문제다.
• 딱 봐도 그리디 스타일의 문제라고 생각하고 바로 예제를 뜯어보았다.
• 예제 1의 경우 [-39, -37, -29, -28, -6, 2, 11]이다.
• 마지막에는 책을 꽂고 원점으로 돌아올 필요가 없으므로 무조건 마지막에 좌우에서 가장 먼 부분의 책을 꽂는 것이 좋다.
• 그렇다면 위 예제에서는 -39 부분을 마지막에 꽂는 것이 좋고 , 책을 한 번에 2권까지 들 수 있으므로 -39를 꽂으러 가는 김에 -37도 꽂고 오면 된다.
• 이후 , [-29, -28, -6, 2, 11] 책만 생각해보자면 , 가장 먼 부분을 꽂고 돌아오면서 m-1개를 순차적으로 꽂으면서 돌아와 주면 된다.
• 즉 -29를 꽂고 m-1개니까 뒤에 1개 더 즉 -28까지 같이 꽂아주고 이동거리 | -29 * 2 | 를 추가해주면 되는 것이다.
• 이처럼 가장 먼 부분부터 꽂아 나가면서 뒤의 m-1을 공짜로 꽂는 방식으로 이동거리를 체크해주면 된다.
• 풀이를 정리하자면 다음과 같다.
• 1. 좌우에서 가장 먼 부분의 책을 꽂고 , 그 이동거리를 정답에 추가하고 , 그 좌우 끝부터 m개의 책을 배열에서 제거한다.
• 2. 이후 가장 먼 부분부터 책들을 m개씩 정리하며 정답에 가장 먼 책 좌표 ( 이동거리 ) * 2 씩 더해주면 된다.
• 생각나는대로 코드를 짰더니 풀이가 너무 지저분 해보인다.
• 깔끔한 코드와 풀이는 다른 블로그를 참고하자.

 

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().split(" "))
check_list = list(map(int,sys.stdin.readline().split(" ")))
check_list.sort()
m_list = deque()
p_list = []

for i in check_list:
    if i < 0:
        m_list.append(i)
    else:
        p_list.append(i)

ans = 0
if not p_list:
    p_list.append(0)
if not m_list:
    m_list.append(0)

if abs(min(m_list)) < max(p_list):
    ans += p_list[-1]
    for i in range(m):
        if p_list:
            p_list.pop(-1)
        else:
            break
elif abs(min(m_list)) > max(p_list):
    ans += abs(m_list[0])
    for i in range(0,m):
        if m_list:
            m_list.popleft()
        else:
            break
else:
    if len(m_list) > len(p_list):
        ans += abs(m_list[0])
        for i in range(0, m):
            if m_list:
                m_list.popleft()
            else:
                break
    else:
        ans += p_list[-1]
        for i in range(m):
            if p_list:
                p_list.pop(-1)
            else:
                break

for i in range(0,len(m_list),m):
    ans += (abs(m_list[i]) * 2)
for i in range(len(p_list)-1,-1,-m):
    ans += (p_list[i] * 2)
print(ans)

---