[백준] Python 1461번 도서관 골드5 - 그리디

swb·2022년 11월 30일
0

백준

목록 보기
14/18

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

접근 방법

  1. 최솟값을 찾기 위해서는 가장 큰 값을 마지막에 들려야 한다.
  2. 정렬을 하여 모두 들려준 뒤 가장 큰 값을 빼면 된다.
  3. 한번에 M만큼 점프할 수 있다고 생각하면 편하다.
    예를 들어 M = 2, 책의 위치 = [1, 2, 3, 4, 5]가 있을 때
    한번에 2, 4 이런 식으로 가면 된다.
  4. 주의할 점은 순차적으로 가면 2->4->5 이런식이 된다.
    그렇게 되면 22 + 42 + 5 = 17이 되고
    뒤에서 부터 간다면 42 + 22 + 1 = 13이 된다. 음수는 순차적으로 가면 될 것이다.
  5. 음수와 양수를 따로 나눠서 이동하면 편할 것이다.

풀이

N, M = map(int, input().split())
arr = list(map(int, input().split()))
answer = 0
arr.sort()
pos = 10001
for i in range(len(arr)):
    if arr[i] > 0:
        pos = i # 양수 위치 찾기
        break

if N == 1: # N이 1인 경우
    answer = abs(arr[0])
elif pos == 10001: # 양수가 없는 경우
    for i in range(0, N, M): # 모든 원소 계산
        answer += abs(arr[i]) * 2
    answer -= abs(arr[0])
else:
    for i in range(0, pos, M): # 양수 전까지 음수들
        answer += abs(arr[i]) * 2

    for i in range(N-1, pos-1, -M): # 음수 전까지 양수들
        answer += arr[i] * 2

    answer -= max(abs(arr[0]), abs(arr[-1])) # 가장 큰 값 빼기
print(answer)
profile
개발 시작

0개의 댓글