[파이썬] 백준 18513 : 샘터 (골드4)

[파이썬] 백준 18513 : 샘터 (골드4)

18513번: 샘터

---

문제

---

풀이

0. 방향성 생각

• 입력 범위 매우 크다 -> 자료구조?
• 우물과 우물 사이 공간을 2개로 분리한다. 
• 우물 좌우에 각각 몇개의 집을 지을 수 있는지 체크
• 힙에 (우물로부터 가장 가까운 집, 남은 공간, 우물 좌표)를 넣는다.

1. 입력

import heapq as hq
import sys
input = lambda: sys.stdin.readline().rstrip()

n,k = map(int,input().split())
water = list(map(int,input().split()))
water.sort()

• 대소관계 뒤바뀌지 않게 정렬 한 번.

2. 힙 저장

heap = []
for i in (0,-1):
    hq.heappush(heap,(1,10**6,water[i]))

for i in range(len(water)-1):
    l,r = water[i:i+2]
    space = r-l-1
    if space:
        p,q = divmod(space,2)
        hq.heappush(heap,(1,p+q,l))
        if p:
            hq.heappush(heap,(1,p,r))

• 왼쪽 끝점은 왼쪽에 최대 10**6개 건설 가능. 오른쪽도 마찬가지
• 두 집과 집 사이 공간을 2개로 분할
• 홀수인 경우 왼쪽 집이 가져가는거로

3. 출력

score = 0
for _ in range(k):
    d,space,x = hq.heappop(heap)
    score += d
    if space-1:
        hq.heappush(heap,(d+1,space-1,x))
print(score)

• 집을 k개 지을때까지 계속 반복하기
• 어떤 우물 x 근처에 공간이 없으면 힙에 추가하지 않는다.

 

---

전체코드

import heapq as hq
import sys
input = lambda: sys.stdin.readline().rstrip()

n,k = map(int,input().split())
water = list(map(int,input().split()))
water.sort()

heap = []
for i in (0,-1):
    hq.heappush(heap,(1,10**6,water[i]))

for i in range(len(water)-1):
    l,r = water[i:i+2]
    space = r-l-1
    if space:
        p,q = divmod(space,2)
        hq.heappush(heap,(1,p+q,l))
        if p:
            hq.heappush(heap,(1,p,r))

score = 0
for _ in range(k):
    d,space,x = hq.heappop(heap)
    score += d
    if space-1:
        hq.heappush(heap,(d+1,space-1,x))
print(score)

 

코멘트

오타난거 체크 못하고 계속 삽질...

밥먹고 오니까 보임... 사람은 밥을 먹어야...