[백준/파이썬] 1461 도서관

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

---

알고리즘 분류

• 그리디

문제풀이

가장 최소 걸음 수를 위해서는 우선 음수, 양수를 분리한다.
그리고 마지막 책은 제자리에 놔둔 후 다시 0으로 돌아올 필요가 없기 때문에 절댓값으로 가장 큰 위치 책+M개의 책은 마지막에 가져와야 한다.

예시의 경우 각 리스트는 다음과 같다.
plus=[11,2]
minus=[-39,-37,-29,-28,-6]
lst=[11,-29,-6] 해당 리스트로부터 왕복생각해서 X2하면 131

소스코드

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

plus=[]
minus=[]
for i in loc:
  if i>0:
    plus.append(i)
  else:
    minus.append(i)

plus.sort(reverse=True)
minus.sort()

max_value=0
for i in loc:
  if abs(i)>abs(max_value):
    max_value=i

lst=[]
for i in range(0, len(plus), m):
  if plus[i]!=max_value:
    lst.append(plus[i])
    
for i in range(0, len(minus), m):
  if minus[i]!=max_value:
    lst.append(minus[i])

result=abs(max_value)
for i in lst:
  result+=abs(i*2)
print(result)