백준_1461_도서관(python)

★ 접근 방식

- 입력에서 n,m의 최대 크기가 50이라고 했을 때 모든 경우의 수를 다 보아도 시간측면에서 크게 무리가 안 갈 것이라고 생각했다. 처음에는 이분탐색, 그리디라고 생각했다. 이분탐색을 쓰기에는 기준이 될 만한 값이 없어서 그리디라고 결정지었다.

 

★ 풀이

- 마지막에는 원 점으로 돌아오지 않아도 되기에 절댓값이 맨 왼 쪽이 클지, 맨 오른쪽이 클 지 생각하는 두 가지 경우가 있다. 여러 조건문을 써가면서 절댓값이 어느 쪽이 더 클 지, -의 부호로만 이루어져 있을 지, +로만 이루어져 있을 지로 풀어 볼 수 있지만 너무 난잡해질 것 같애서 맨 왼쪽이 더 크다고 가정한 함수, 맨 오른쪽이 더 크다고 가정한 함수 두개를 비교해서 더 작은 값을 리턴한 것을 출력해줬다.

 

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

data = list(map(int,input().split()))
data.append(0)
data.sort()
zero_idx = data.index(0)

# 왼쪽 *1, 오른쪽 * 1

def left_multione():
    count = 0
    if zero_idx == 0:
        return float("inf")
    i = 0
    flag = 0
    while i < zero_idx:
        if flag == 0:
            count += abs(data[i])
            flag = 1
        else:
            count += abs(data[i]) * 2
        i += m
    i = len(data) - 1
    while i > zero_idx:
        count += abs(data[i]) * 2
        i -= m
    return count
def right_multione():
    count = 0
    if zero_idx == len(data) - 1:
        return float("inf")
    flag = 0
    i = len(data) - 1
    while i > zero_idx:
        if flag == 0:
            count += abs(data[i])
            flag = 1
        else:
            count += abs(data[i]) * 2
        i -= m
    i = 0
    while i < zero_idx:
        count += abs(data[i]) * 2
        i += m
    return count
result = float("inf")
result = min(result,left_multione())
result = min(result,right_multione())
print(result)