[BOJ/백준] 18513 샘터 파이썬

문제 링크 : https://www.acmicpc.net/problem/18513

18513번: 샘터

 

각각의 샘터에서 좌우로 집을 하나씩 집을 놔보고, 그리고 그 집 양옆으로 집을 하나씩 놔보면 결국 불행도가 최소로 되게 집이 위치하게 된다.

그래서 큐에 집의 좌표를 넣고 집이 k개가 될 때 까지 수행해주면 된다.

결국 BFS를 수행하면 된다.

 

문제는 범위이다. 샘터는 -1억에서+1억까지다. 거기까지이고 집까지 놀 위치를 고려한다면 2억개가 넘는다. 따라서 그냥 배열로 한다면 메모리 초과가 날 것이다. 그래서 나도 처음에는 메모리 초과가 났다.

이를 좀 줄여보려고 샘터 사이의 거리가 k가 넘는 다면 줄여주고 등등 여러 방법을 생각해봤지만 다 포기하고 단순하게 생각했다.

 

어차피 집은 필요한 좌표는 집을 놓을 좌표이다. 그래서 최대 10만개 이므로 딕셔너리를 사용했다.

좌표를 키로하고 값을 거리로 하는 딕셔너리를 만들어 풀이 했다.

 

그래서 현재 점에서 좌우 좌표가 딕셔너리에 있는지에 따라 해당방향을 큐에 넣을지 정했다.

그리고 큐에 넣으면서 집의 개수를 증가 시켜줬는데 이때 집의 개수가 k가 된다면 종료 해줬다.

 

from sys import stdin
from collections import deque

input = stdin.readline
n,k = map(int, input().split())

points = list(map(int, input().split()))

home_dict = {}

q = deque()
answer = 0
for p in points:
    home_dict[p] = 0
    q.appendleft((p,0))

def solv():
    global answer
    h_cnt = 0
    while q:
        now, cnt = q.pop()

        if now-1 not in home_dict:
            q.appendleft((now-1, cnt+1))
            home_dict[now-1] = cnt+1
            answer += cnt+1
            h_cnt += 1
            if h_cnt == k:
                break

        if now+1 not in home_dict:
            q.appendleft((now+1, cnt+1))
            home_dict[now+1] = cnt+1
            answer += cnt+1
            h_cnt += 1
            if h_cnt == k:
                break

    print(answer)
solv()