[BOJ] 1461. λ„μ„œκ΄€(πŸ₯‡5)

yijin3018Β·6일 μ „
0

PS_BOJ

λͺ©λ‘ 보기
1/1

1. SOURCE

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

2. IDEA

-37 2 -6 -39 -29 11 -28

ν•΄λ‹Ή 배열을 μ •λ ¬ν•œλ‹€λ©΄ μ•„λž˜μ™€ κ°™λ‹€. κ°€μž₯ λ¨Ό κ±°λ¦¬λŠ” -39μ΄λ―€λ‘œ ν•΄λ‹Ή μœ„μΉ˜μ— 갈 λ•ŒλŠ” μ±…μ˜ κ°œμˆ˜μ— 따라 -37, -29와 같은 μœ„μΉ˜λ₯Ό κ±°μ³μ„œ 도달할 수 μžˆλ‹€. 예제1κ³Ό 같은 경우, 책을 2κ°œμ”© λ“€ 수 있기 λ•Œλ¬Έμ— 0μ—μ„œ 였λ₯Έμͺ½μ˜ 경우 2λ₯Ό κ±°μ³μ„œ 11κΉŒμ§€ κ°”λ‹€κ°€ λŒμ•„μ˜¬μˆ˜μžˆλ‹€. μ™Όμͺ½μœΌλ‘œλŠ” -39, -29, -6의 μœ„μΉ˜λ₯Ό 찍고 λŒμ•„μ˜¬ 수 μžˆλ‹€. ν•˜μ§€λ§Œ μ΅œμ†Œ 거리λ₯Ό μœ„ν•΄μ„œλŠ” κ°€μž₯ λ¨Ό κ±°λ¦¬λŠ” μ™•λ³΄ν•˜μ§€ μ•ŠκΈ° λ•Œλ¬Έμ— -37을 κ±°μ³μ„œ -39λ₯Ό κ°€λŠ” 것이 거리λ₯Ό λ‹¨μΆ•μ‹œν‚¬ 수 μžˆλŠ” 아이디어이닀.

-39 -37 -29 -28 -6 (0) 2  11

3. SOLUTION

3-1. Heap

κ°€μž₯ λ¨Όμœ„μΉ˜λ₯Ό μ°ΎκΈ° μœ„ν•΄μ„œ λ°°μ—΄μ˜ μ΅œλŒ€κ°’κ³Ό μ΅œμ†Œκ°’ 쀑 큰 값을 μ €μž₯ν•΄μ€€λ‹€.

heap을 ν™œμš©ν•΄μ„œ 풀이 κ°€λŠ₯ν•˜λ‹€.
0을 κΈ°μ€€μœΌλ‘œ 움직이기 λ•Œλ¬Έμ— μ–‘μˆ˜νž™κ³Ό μŒμˆ˜νž™μœΌλ‘œ λ‚˜λˆˆλ‹€.
λ„£μ–΄μ€€ λ¦¬μŠ€νŠΈμ—μ„œ 정렬을 ν•΄μ•Ό 0μ—μ„œ κ°€μž₯ λ¨Ό 거리뢀터 정렬을 ν•΄μ•Ό ν•˜λ―€λ‘œ heap을 μ‚¬μš©ν•˜λ©΄ λ¦¬μŠ€νŠΈμ— λ„£κΈ°λΆ€ν„° μ •λ ¬κΉŒμ§€ ν•œλ²ˆμ— ν•΄κ²°ν•  수 μžˆλ‹€.

각각의 νž™μ΄ μ‘΄μž¬ν•  λ•Œ, ν•˜λ‚˜λ₯Ό λ½‘μ•„μ„œ distance에 λ”ν•œλ‹€. 총 M개의 책을 λ“€ 수 있기 λ•Œλ¬Έμ— λ‚˜λ¨Έμ§€ M-1개의 책은 νž™μ΄ μ‘΄μž¬ν•˜λ©΄ λ½‘κΈ°λ§Œ ν•˜κ³  λ”ν•˜μ§€λŠ” μ•ŠλŠ”λ‹€. 총 M개의 μ±… μ€‘μ—μ„œ 첫번째 책은 κ±°λ¦¬λŠ” λ”ν•˜κ³  λ‚˜λ¨Έμ§€λŠ” κ±΄λ„ˆ 뛰도둝 κ΅¬ν˜„λœλ‹€.

μ΄λ ‡κ²Œ λ”ν•œ distanceλŠ” 음수이기 λ•Œλ¬Έμ— μ–‘μˆ˜λ‘œ λ§Œλ“€μ–΄μ„œ 2λ°° ν•΄μ£Όκ³  κ°€μž₯ λ¨Ό 거리도 더해쀬기 λ•Œλ¬Έμ— largestλ₯Ό λΉΌμ€€λ‹€.

3-2. List

μ΅œμ†Œκ°’, μ΅œλŒ€κ°’μ˜ μ ˆλŒ€κ°’μ„ λΉ„κ΅ν•˜μ—¬ 졜μž₯거리λ₯Ό μ°Ύμ•„μ€€λ‹€.
μœ„μΉ˜λ₯Ό μ–‘μˆ˜, 음수둜 λ‚˜λˆ μ„œ 리슀트둜 각각 λ§Œλ“€μ–΄μ£Όκ³  λ‚΄λ¦Όμ°¨μˆœμœΌλ‘œ μ •λ ¬ν•΄μ€€λ‹€.
빈 리슀트 answer에 Mμ”© κ±΄λ„ˆλ›°λ©° 각각의 리슀트의 μ›μ†Œλ₯Ό μ €μž₯ν•΄μ€€λ‹€. μ΄λ•Œ, ν•΄λ‹Ή μ›μ†Œκ°€ 졜μž₯거리가 아닐 κ²½μš°μ—λ§Œ μ €μž₯ν•˜μ—¬ 리슀트 answer을 μƒμ„±ν•œλ‹€. μ΄λ ‡κ²Œ λ§Œλ“€μ–΄μ§„ λ¦¬μŠ€νŠΈλŠ” μ›μ†Œλ§ˆλ‹€ 2λ°°μ”© κ³±ν•΄μ„œ λ”ν•˜κ³  졜μž₯거리만 ν•œλ²ˆ 더해 정닡을 μΆœλ €ν•΄μ€€λ‹€.


4. CODE

4-1

import sys
input = sys.stdin.readline
import heapq

N, M = map(int ,input().split())
books = list(map(int ,input().split()))

largest = max(max(books), -min(books))
pos_heap, neg_heap = [], []
for book in books:
    if book >= 0:
        heapq.heappush(pos_heap, -book)
    else:
        heapq.heappush(neg_heap, book)

distance = 0

while pos_heap:
    distance += heapq.heappop(pos_heap)
    for _ in range(M-1):
        if pos_heap:
            heapq.heappop(pos_heap)
while neg_heap:
    distance += heapq.heappop(neg_heap)
    for _ in range(M-1):
        if neg_heap:
            heapq.heappop(neg_heap)

print(-distance * 2 - largest)

4-2

import sys
input = sys.stdin.readline
import math

N, M = map(int, input().split())
books = list(map(int, input().split()))
positive, negative = [], []

largest = max(abs(min(books)), abs(max(books)))

for loc in books:
    if loc > 0:
        positive.append(loc)

    else:
        negative.append(abs(loc))

def append_dist(target_list, m):
    for i in range(0, len(target_list), m):
        if target_list[i] != largest:
            answer.append(target_list[i])
    return answer

positive.sort(reverse=True)
negative.sort(reverse=True)
answer = []
answer = append_dist(positive, m)
answer = append_dist(negative, m)
total = 0
for ans in answer:
    total += (ans*2)
total += largest

print(total)
profile
πŸ’» For Computer Science..

0개의 λŒ“κΈ€