[골드4]백준 1461번(웰컴 키트) - 코테공부 28일차(2025.02.19)

문제유형

그리디 알고리즘

풀이 방법 도출 과정

1. 이동 횟수 계산

- 한 번에 M권의 책을 옮길 수 있으므로, 책들을 배치할 때 N//M번은 배치 후 0으로 돌아와야한다.

- 마지막 배치에서는 복귀할 필요가 없으므로, 복귀 거리를 제외할 수 있다.

2. 거리 최적화

- 한 번에 옳길 책은 서로 가까운 위치에 있는 것이 이동 거리를 줄이는 데 유리하다.

- 따라서 책의 좌표를 정렬(sort)하여, 가까운 위치부터 묶어 처리할 수 있도록 한다.

3. 알고리즘 선택

- 위 전략은 각 이동 시 최적의 선택을 하는 그리디 알고리즘에 기반한다. 

- 매 이동마다 가장 먼 지점까지 이동한 후, M권의 책을 배치하고(마지막 배치 제외 시 복귀 생략) 복귀하는 방식으로 전체 걸음 수를 최소화할 수 있다. 

시간 복잡도

시간 복잡도는 입력에서 O(N) 정렬에서 O(NlogN) for문에서 O(N)인데 곱하기가 아니라 더하기 이기 때문에 O(NlogN)이다. 

코드 및 간단설명

그리디 연산을 이용하였다. 

# 입력 받기
N, M = map(int, input().split())
positions = list(map(int, input().split()))

# 1. 좌표를 양수와 음수로 분리
positives = []  # 0보다 큰 좌표 (오른쪽)
negatives = []  # 0 이하의 좌표 (왼쪽)
for pos in positions:
    if pos > 0:
        positives.append(pos)
    else:
        negatives.append(pos)

# 2. 양쪽에서 가장 먼 거리가 제일 먼저 오도록 정렬
# 오른쪽: 내림차순 (가장 큰 값부터)
positives.sort(reverse=True)
# 왼쪽: 음수이므로 오름차순 정렬하면 절댓값 기준 내림차순 효과가 있음.
negatives.sort()

total_distance = 0

# 3. 오른쪽(양수)에서 M권씩 옮기기: 각 그룹마다 가장 먼 위치까지 갔다가 복귀
for i in range(0, len(positives), M):
    total_distance += 2 * positives[i]

# 4. 왼쪽(음수)에서 M권씩 옮기기: 각 그룹마다 가장 먼 (절댓값이 큰) 위치까지 갔다가 복귀
for i in range(0, len(negatives), M):
    total_distance += 2 * abs(negatives[i])

# 5. 마지막 배치는 복귀하지 않아도 되므로, 전체 이동 거리에서 
#    오른쪽과 왼쪽 중 가장 먼 거리를 한 번 빼준다.
max_distance = 0
if positives:
    max_distance = max(max_distance, positives[0])
if negatives:
    max_distance = max(max_distance, abs(negatives[0]))

total_distance -= max_distance

print(total_distance)