[BOJ] 도서관 (1461, G4)

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

 

 

가장 멀리 있는 책은 뒤에 가져가서 놔두고.. 가까운 책은 그냥 왕복 해도 된다.
그리고 여러 권 들 수 있으면 가장 가까이 있는 책들은 몰아서 가져가면 된다....

네.! 그리디하게 풀면 됩니다.

가장 먼저 드는 생각 / sort해서 책에 들 수 있는 개수 만큼씩 나눠 가자.
그러면, 그냥 쉽게 최대 거리 계산 찍고, 마지막만 멈추면 끝!!

 

 

 

 

 

일까요?

 

 

 

 

 

 

 

네! 당연히 틀렸습니다!

문제가 생기는 지점은 테케로도 제공되는데 바로, 양수 방향과 음수 방향이 섞일 때입니다.
양수와 음수가 섞이면 0을 거쳐서 다시 왔다갔다 해야 합니다. 효율적이지 않습니다.

여기서 하나 관찰할 수 있는데 양수와 음수가 섞이면 어차피 0에서 책을 덜 들고 출발하는 것과 동일합니다.

어?  양수와 음수 케이스를 분리하면 되겠군요!  절댓값으로 가장 작은 세트부터 처리해줍시다.!

 

이럼, 깔끔하게 정답입니다. 간단한 그리디 문제입니다!

# 도서관
# 양수 방향과 음수 방향을 별도로 나눠 처리.
import sys
input = sys.stdin.readline
book, hand = map(int, input().split())
goal_list = list(map(int, input().split()))

plus_list = []
minus_list = []
for g in goal_list:
    if g > 0:
        plus_list.append(g)
    elif g < 0:
        minus_list.append(g)
plus_list.sort(reverse = True) # 플러스는 큰 거부터 묶는다.
minus_list.sort(reverse = False) # 마이너스는 작은 거부터 묶는다.
goal = []
# 플 마가 섞이는거? 사실 왕복 서로 찍어야 해서 나눠 드는거랑 큰 차이가 없다.
for i in range(0, len(plus_list), hand):
    end_point = min(i+hand, len(plus_list))
    cur_list = plus_list[i:end_point]
    goal.append(cur_list[0])
for i in range(0, len(minus_list), hand):
    end_point = min(i+hand, len(minus_list))
    cur_list = minus_list[i:end_point]
    goal.append(-cur_list[0])
goal.sort(reverse = False)
answer = 0
for i in range(len(goal)):
    if i != len(goal)-1:
        answer += 2*goal[i]
    else:
        answer += goal[i]
print(answer)