[BOJ] 1461번 : 도서관

🔒 문제

⌨ 입력

🖨 출력

📚 예제

📌 풀이

1. 책의 위치를 받은 배열을 음의 정수(minus_loca)와 양의 정수(plus_loca) 두 개의 배열로 나눈다.

2. 음의 정수들을 배열에 넣을 때, 계산하기 편하게 -1을 곱해서 넣는다.

3. -1을 곱한 음의 정수와 양의 정수를 내림차순으로 배열에 넣는다.

=> 가장 큰 보폭인 애들끼리 묶어서 최대한 많은 양을 옮기기 위해

4. 음의 정수와 양의 정수 각각을 M칸씩 건너 뛰면서 새로운 배열(minus_step, plus_step)에 저장한다.

=> 최대로 들 수 있는 책의 개수만큼 옮길 책들의 묶음을 나눠줌

5. steps를 계산해준다.

5-1. minus_step의 인수 수가 0 인 경우, plus_step의 가장 큰 값은 steps에 한번만 더해주고, 나머지 값들은 2배를 해서 더해준다.

5-2. plus_step 의 인수 수가 0 인 경우, minus_step의 가장 큰 값은 steps에 한번만 더해주고, 나머지 값들은 2배를 해서 더해준다.

5-3. 둘다 인수의 수가 0이 아닌 경우, minus_step의 최댓값과 plus_step의 최댓값 중 더 큰 수를 한번만 더해주고, 나머지 값들은 2배를 해서 더해준다.

이제 steps를 다 구했다.

백준의 예제1과 예제2를 통해 1~5 과정을 다시 살펴보자

🔑 python 코드

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
locations = [int(x) for x in input().split()]
minus_loca = []
plus_loca = []
steps = 0

for i in locations:
    if(i < 0): minus_loca.append(i * -1)
    else: plus_loca.append(i)
minus_loca.sort(reverse = True) # 오름차순 정렬
plus_loca.sort(reverse = True) # 내림차순 정렬

def find_step(loca):
    list = []
    for i in range(0, len(loca), M):
        list.append(loca[i])
    return list

minus_step = find_step(minus_loca)
plus_step = find_step(plus_loca)

# case1 : 음수 위치가 없음
if(len(minus_step) == 0):
    steps += plus_step.pop(0) # 멈추는 위치
    steps += sum(plus_step) * 2

# case2 : 양수 위치가 없음
elif(len(plus_step) == 0):
    steps += minus_step.pop(0) # 멈추는 위치
    steps += sum(minus_step) * 2

# case3 : 둘 다 있음
else:
    # 멈추는 위치는 음수 양수 중 더 큰 쪽으로 함
    if(minus_step[0] > plus_step[0]):
        steps += minus_step.pop(0)
    else:
        steps += plus_step.pop(0)

    # 남은 위치들은 왕복하기 때문에 2배를 해줌
    steps += (sum(plus_step) + sum(minus_step)) * 2

print(steps)