[백준] 1461번:도서관 (python 파이썬)

www.acmicpc.net/problem/1461

1461번: 도서관

풀이

예제 입력으로 보자.

7 2

-37 2 -6 -39 -29 11 -28

 

먼저, 음수부분과 양수부분을 나눠준다.

음수부분 -> minus 리스트에 abs() 절대값을 씌워준 후, 내림차순 정렬 [39, 37, 29, 28, 6]

양수부분 -> plus 리스트에 내림차순 정렬 [11, 2]

 

직접 계산을 해보면 쉽게 알겠지만, 책 두 개를 가지고 11들렸다가 2들렸다가 제자리로 돌아가는 걸음의 수 = 11*2 와 같다.

m으로 나눠지지 않은 남은 리스트 값들로 계산해봐도 큰 수*2 를 하면 범위 내 리스트에 들렸다가 제자리로 돌아가는 걸음의 수가 된다.

 

문제 조건에서 책을 모두 제자리에 놔둔 후에는 다시 제자리로 올 필요가 없기 때문에 제일 큰 값에 대해서만 예외 처리를 해주면 된다.

 

따라서,

minus 리스트에서 m으로 나눠지는 인덱스들, len(minus)%m>0 이라면 가장 끝에 있는 값 -> count 리스트에 삽입

plus 리스트에서 m으로 나눠지는 인덱스들, len(plus)%m>0 이라면 가장 끝에 있는 값 -> count 리스트에 삽입

후 오름차순 정렬한 다음,

가장 큰 값 하나만 한 번만 더하고 나머지 값에 대해서는 합한 후 2배 해주면 된다.

 

 

소스코드

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

plus = []
minus = []
count = []

//양수와 음수부분을 나눠주되, 음수부분은 절대값을 씌워줌
for i in book:
    if i>0:
        plus.append(i)
    else:
        minus.append(abs(i))

//내림차순으로 정렬
plus.sort(reverse=True)
minus.sort(reverse=True)

//m*i 번째 리스트를 count 리스트에 추가. if문을 통해 남는 리스트 중 가장 큰 값을 count에 넣어준다.
for i in range(len(plus)//m):
    count.append(plus[i*m])
if len(plus)%m>0:
    count.append(plus[(len(plus)//m)*m])

for i in range(len(minus)//m):
    count.append(minus[i*m])
if len(minus)%m>0:
    count.append(minus[(len(minus)//m)*m])

count.sort()

//마지막에는 제자리로 돌아올 필요가 없기 때문에 최대값만 그냥 result에 넣고 나머지는 2를 곱해 더한다.
result = count.pop()
result += 2*sum(count)

print(result)