[Python] 그리디 - 1461. 도서관(골4)

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

1461번: 도서관

 

>>문제 포인트

- 음수와 양수값을 나누어 생각해야 함.

- 긴 길이 순으로 묶어 한번에 책을 가져다주어야 함.

- 마지막에 0으로 돌아올 의무가 없으므로 가장 긴 거리 한번을 빼주기

 

 

예를 들어 한번에 들 수 있는 책이 2권이고

위치가 -37 2 -6 -39 -29 11 -28이라면 

 

음수 위치 = [-39 , -37 , -29, -28, -6]

양수 위치 = [11 , 2]

 

로 나눌 수 있음

 

그럼 2권씩 묶어 왕복 처리

 

음수거리

1회 : (-39, -37)        거리 :  + 39*2     // 78 

2회 : (-29, -38)        거리 :  + 29*2     // 136

3회 : (-6, )               거리 :  + 6*2       //  148

 

정수거리

1회 : (11, 2)        거리 :  + 11*2          //  160

 

마지막 회차에는 0으로 돌아올 의무가 없으므로

절대값이 가장 큰 39값 빼주기 -39          //131

 

 

>>코드

#걸리는 시간 계산
def time(k, book):
  a=0
  #그룹 내 가장 긴거리 즉, 그룹의 첫번째 요소들만 더해주기
  for i in range(0,len(k),book):
    a+=k[i]*2

  return a


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

#양수 음수 나눠받기
negative=[]
positive=[]

for i in loc:
  if i<0:
    negative.append(i)
  else:
    positive.append(i)

#절대값 처리로 긴거리순 정렬
negative = sorted(map(abs,negative), reverse=True)
positive= sorted(positive,reverse=True)

#시간 계산
result=0
result += time(negative, book)
result += time(positive, book)

# 위치내 가장 긴 거리 한번 빼주기
result -= max(map(abs, loc))

print(result)