백준 1461 도서관 파이썬

www.acmicpc.net/problem/1461

1461번: 도서관

def right_move(A, zero_index, M):
    right_len = len(A) - (zero_index + 1)
    left_len = zero_index
    ans = 0
    remain_right = right_len % M

    if remain_right != 0:
        ans+=A[zero_index+remain_right] * 2


    for i in range(zero_index+remain_right+M, len(A), M):
        if i == len(A) - 1:
            ans+=A[i]
        else:
            ans+=A[i]*2
            
    return ans
    
def right_first(A, zero_index, M):
    right_len = len(A) - (zero_index + 1)
    left_len = zero_index
    ans = 0
    remain_right = right_len % M

    if remain_right != 0:
        ans+=A[zero_index+remain_right] * 2


    for i in range(zero_index+remain_right+M, len(A), M):
        ans+=A[i]*2

    remain_left = left_len % M

    if remain_left != 0:
        if zero_index-remain_left == 0:
            ans+=abs(A[zero_index-remain_left])
        else:
            ans+=abs(A[zero_index-remain_left]) * 2

    for i in range(zero_index-remain_left-M, -1, -M):
        if i == 0:
            ans+=abs(A[i])
        else:
            ans+=abs(A[i]) * 2
            
    return ans

def left_move(A, zero_index, M):
    right_len = len(A) - (zero_index + 1)
    left_len = zero_index
    
    ans = 0
    remain_left = left_len % M
    
    if remain_left != 0:
        ans+=abs(A[zero_index-remain_left]) * 2

    for i in range(zero_index-remain_left-M, -1, -M):
        if i == 0:
            ans+=abs(A[i])
        else:
            ans+=abs(A[i])*2
            
    return ans
    
    
def left_first(A, zero_index, M):
    right_len = len(A) - (zero_index + 1)
    left_len = zero_index
    
    ans = 0
    remain_left = left_len % M

    if remain_left != 0:
        ans+=abs(A[zero_index-remain_left]) * 2

    for i in range(zero_index-remain_left-M, -1, -M):
        ans+=abs(A[i])*2

    remain_right = right_len % M

    if remain_right != 0:
        if zero_index+remain_right == len(A) - 1:
            ans+=A[zero_index+remain_right]
        else:
            ans+=A[zero_index+remain_right] * 2

    for i in range(zero_index+remain_right+M, len(A), M):
        if i == len(A) - 1:
            ans+=A[i]
        else:
            ans+=A[i]*2
                
    return ans
                
    
N, M = map(int, input().split())
A = list(map(int, input().split()))
if len(A) == 1:
    print(A[0])
else:    
    A.sort()
    zero_index = -1
    for i in range(1, len(A)):
        if A[i-1] < 0 and A[i] > 0:
            A.insert(i, 0)
            zero_index = i

    ans = 0
    move_cnt = 1
    if zero_index == -1:
        if A[0] < 0 and A[-1] < 0:
            A.append(0)
            ans = left_move(A, len(A) - 1, M)
        elif A[0] > 0 and A[-1] > 0:
            A.insert(0, 0)
            ans = right_move(A, 0, M)
            
    else:
        # 더 먼 방향을 마지막에 방문 (마지막 방문은 0으로 다시 돌아오지 않아도 되기때문.)
        if abs(A[0]) > abs(A[-1]): # 오른쪽 먼저 
            ans = right_first(A, zero_index, M)
        else:
            ans = left_first(A, zero_index, M)

    print(ans)

 

코드가 좀 많이 너저분하다.

 

우선 이 문제는 책이 쌓여있는 위치와 시작위치가 0 이고, 책을 들수 있는 만큼(M) 들고

정해진 위치까지 걸어가서 꽂은 후, 다시 0으로 돌아오는 과정을 반복하다가 마지막 책은 꽂은후 0으로 돌아오지 않아도 된다.

이 문제를 풀기 위한 아이디어를 몇가지 생각해보면

첫째. 마지막 책은 꽂은후 0으로 돌아오지 않아도 되기 때문에 가장 멀리 있는 책을 마지막에 꽂는 것이 유리하다는 것

둘째. 책의 위치가 양수와 음수이고 시작위치(책이 쌓여있는 위치)가 0이므로 0을 기준으로 양수는 오른쪽, 음수는 왼쪽에 위치한다는걸 알 수 있다.

셋째. 책을 들수 있을만큼 들고 오른쪽 또는 왼쪽으로 책을 꽂을 때 남는 책의 수만큼은 가까운 위치에서 빠르게 다시 0으로 돌아와서 새책을 꽂는게 유리하다.

예를 들어 오른쪽으로 꽂을 책이 5권 [1,2,3,4,5]이 있고 한번에 두권의 책을 들 수 있다고 가정했을때 (M=2) 

알고리즘을 떠나서 상식적으로 생각해보면 1,2 꽂고 0으로 와서 3,4 꽂고 나면 5가 남는데, 남은 한권꽂으려고 다시 5까지 갔다오면 손해가 크다는것이다 이 경우 17 step.

1,2  꽂고 (2 step) 0으로 돌아오고 (2 step) 3, 4 꽂고 (4 step) 다시 0으로 돌아오고 (4 step) 5꽂고 (5 step) = 17 step

그러나 1 꽂고 바로 0으로 돌아와서 2,3 꽂고 0으로 돌아오고 4,5 꽂는게 최선이다. 이 경우는 13 step.

1 꽂고 ( 1step) 0으로 돌아와서(0 step) 2,3 꽂고 (3 step) 0으로 돌아오고 (3 step) 4,5 꽂는다 (5step) = 13 step

그리고 가장 멀리 있는 책은 마지막에 꽂는게 유리하므로 초기 책의 위치 배열을 정렬한 후, 배열의 양 끝에 있는 값중 어느값이 더 큰지 확인하고,

더 큰 값과 반대방향을 먼저 가야한다. 

이 핵심 아이디어만 있으면 나머지는 구현 문제인데, 소스가 너저~분 한게 구현력이 약하다.

물론 좀 더 다듬을 순 있는데, 자연스럽게 짠 코드가 깔끔해졌으면 좋겠다.