[백준] 1461번 파이썬 _ 도서관

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

1461번: 도서관

문제유형 : 그리디

 

문제풀이 : 

• 양수와 음수를 기준으로 나눈다.
• 각각에 대해서 절댓값이 큰것부터 m만큼 묶어서 처리한다. 
• 이때 전체중에서 가장 절댓값이 큰 부분은 갔다가 돌아오지 않게 처리해야하므로 마지막에 한번 빼주면 된다.

 

나는 m이 음수갯수와 양수갯수 모두보다 큰경우 따로 처리를 해줫는데 안해줘도 되긴한다.

 

정답코드 : 

import sys
input = sys.stdin.readline

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

books = list(map(int, input().split()))
books.sort()

abs_books = []

minus_count = 0
plus_count = 0
for i in range(len(books)):
    if books[i] < 0:
        minus_count += 1
    else:
        plus_count += 1
    abs_books.append((i, abs(books[i])))

abs_books.sort(key=lambda x:x[1], reverse=True)

minus = books[0]
plus = books[-1]

max_val = abs_books[0][1]

if m >= minus_count and m >= plus_count:
    min_val = min(abs(minus), abs(plus))
    max_val = max(abs(minus), abs(plus))
    print(2*min_val + max_val)
    exit()

minus_books = books[:minus_count]
plus_books = books[minus_count:]
plus_books.sort(reverse=True)

cnt = 0
answer = 0
for i in minus_books:
    print(cnt,i, answer)
    if cnt==0:
        answer += 2*abs(i)
    if cnt == m-1:
        cnt = 0
    else:
        cnt += 1

cnt = 0
for i in plus_books:
    print(cnt, i, answer)
    if cnt==0:
        answer += 2*abs(i)
    if cnt == m-1:
        cnt = 0
    else:
        cnt += 1

print(answer-max_val)