문제

문제 이해

문제를 생각해내고 풀이를 작성하는 것 모두가 아직의 나에게 좀 어렵다.

이 문제는 직선상에서 어떤 점(좌표)에 효율적이게 다녀와야한다.

그리디 조건

1. 멀리있는 것 부터 가야 효율적이다.
2. 음수와 양수를 왔다갔다하면 비효율적이다.(한번 탐색할때 한쪽만 하는게 좋음)
3. 무조건 책을 가득 챙겨야 효율적이다.

애초에 이런식으로 조건들이 있으면 그리디인 확률이 높다. 다만 이런 조건들에 다맞춰서 풀이를 고안하고 코드를 짜는게 힘들다. 코딩테스트를 풀기위해서 이런 문제를 푸는 것도 이 두가지 능력을 키우기 위함이다.

먼저 양수와 음수를 다른 배열에 넣는다. 멀리있는 것을 먼저 처리해야한다. 우린 배열의 앞에서 부터 처리하는 로직을 짤것이기 때문에 내림차순으로 정렬한다.(음수는 양수로 바꿔준다. 어차피 양수/음수 배열을 따로 만들기 때문에 이렇게 해도 상관없다.)

이렇게 정렬된 값이 있다고 하자

39 32 29 23 15 0

M=2라면, 39에 갔다가 오는데 39*2 = 78의 거리가 든다. 왜냐하면 어차피 39를 오가는 길에 32가 있어서 39만 카운트하면 된다.

다음 스텝은 29다. 29를 오가면서 23도 들리게 된다. 29*2 = 58의 거리다. 애초에 0에서부터 떨어진 거리라서 한스텝에 0을 한번 가는 카운트가 된다.

마지막 스텝은 15다. 이런 방식으로 두개씩 잘라서 거리의 두배를 계산하면 된다.

이 과정을 편하게 하기 위해서 파이썬의 "슬라이싱"을 사용한다. 배열 arr이 있다면, arr[start:stop:step]이다. start는 시작, stop끝, step은 그 갯수대로 끊는다. 즉, 위에서 예시를 든 것을 arr리스트에 있다고 가정하면, arr[::2]는 첫 값인 39, 두칸 뒤의 값인 29, 마지막으로 15를 반환한다. 이를 이용해서 문제를 풀 수 있다.

코드

# 백준 1461번 도서관

# 책의 개수N, 한번에 들 수 있는 책의 개수M
N, M = map(int, input().split())
arr = map(int, input().split())

# 양수/음수를 각각 넣어줄 배열
positive = []
negative = []

for value in arr:
    if value > 0: # 양수면 positive
        positive.append(value)
    else: # 음수면 negative
        negative.append(-value) # 값을 양수로 전환해서 넣어준다

# 내림차순으로 정렬
positive = sorted(positive, reverse=True)
negative = sorted(negative, reverse=True)

distance = []

# 처음부터 끝까지 M을 스텝으로 꺼낸다
for step in positive[::M]: # 양수 값 처리
    distance.append(step)

for step in negative[::M]: # 음수 값 처리(이전에 부호 바꿔서 양수이긴 하다)
    distance.append(step)

total_sum = 0
# 마지막 값을 가면 돌아올 필요가 없다. 어쨋든 최단거리면 가장큰 값을 마지막에 간다고 생각하고 제외해야 하는듯
total_sum = 2 * sum(distance) - max(distance)

print(total_sum)

total_sum에서 distance의 max값을 빼주는 이유는, 마지막 값은 되돌아올 필요가 없기 때문에 가장 큰 값을 마지막에 간다고 생각하면 되는 것 같다.