213. 공유기 설치

1) 어떤 전략(알고리즘)으로 해결?

Parametric Search

가장 인접한 두 공유기 사이 거리를 최대로 하는 문제(최적화)

를 아래로 변경하는 것

거리 d가 주어졌을 때 공유기 사이의 거리를 d 이상으로 하면서 c개의 공유기 설치 가능한 지 결정하는 문제

2) 코딩 설명

<내 풀이>

import sys

n,c =  map(int, sys.stdin.readline().rstrip().split())
# left 는 1, right = 10^9
# mid 거리로 c개 공유기 설치가능한 지 확인
# 설치가능하다면 더 멀리 배치해도 되니깐 l 을 mid+1
# 아니라면 mid-1
# 조건은 l<=r 

homelist=[];l=1; r = 10**9
for i in range(n) : homelist.append(int(sys.stdin.readline().rstrip()))
homelist.sort()
while l<=r : 
    mid = (l+r)//2 # 가장 인접한 두 공유기 사이의 거리 후보
    now_home = homelist[0]
    possible_home=[now_home]

    for ho in range(1,len(homelist)):
            if homelist[ho]-now_home>=mid:
                now_home=homelist[ho]
                possible_home.append(now_home)
    #print(mid, possible_home)
    if len(set(possible_home))>=c:
        l=mid+1; answer=mid # 정답 후보군 (매번 갱신예정)
    else :
        r=mid-1

print(answer)

🤓

<내 틀렸던 풀이, 문제점>

6%까지 가고 시간초과!

import sys

n,c =  map(int, sys.stdin.readline().rstrip().split())
# left 는 1, right = 10^9
# mid 거리로 c개 공유기 설치가능한 지 확인
# 설치가능하다면 더 멀리 배치해도 되니깐 l 을 mid+1
# 아니라면 mid-1
# 조건은 l<=r 

xlis=[];l=1; r = 10**9
for i in range(n) : xlis.append(int(sys.stdin.readline().rstrip()));xlis.sort()
while l<=r : 
    mid = (l+r)//2 # 가장 인접한 두 공유기 사이의 거리 후보
    idx=0
    possible_home=[0]
    while idx<len(xlis) :
        for r in range(idx+1, len(xlis)) :
            if xlis[r] - xlis[idx]>=mid:
                possible_home.append(idx)
                possible_home.append(r)
                idx=r
                break
        else : idx+=1

    #print(mid, set(possible_home))
    if len(set(possible_home))>=c:
        l=mid+1
        answer=mid
    else :
        r=mid-1

print(answer)

• 아마 가능한 집 갯수 구하는 부분 고쳐야할 거 같아

22%에서 시간초과

;로 한 줄에 썼더니 for 문마다 sort()를 계속해줘서 였음;; 황당

import sys

n,c = map(int, sys.stdin.readline().rstrip().split())

left 는 1, right = 10^9

mid 거리로 c개 공유기 설치가능한 지 확인

설치가능하다면 더 멀리 배치해도 되니깐 l 을 mid+1

아니라면 mid-1

조건은 l<=r

homelist=[];l=1; r = 10**9
for i in range(n) : homelist.append(int(sys.stdin.readline().rstrip()));homelist.sort()
while l<=r :
mid = (l+r)//2 # 가장 인접한 두 공유기 사이의 거리 후보
now_home = homelist[0]
possible_home=[now_home]

for ho in range(1,len(homelist)):
        if homelist[ho]-now_home>=mid:
            now_home=homelist[ho]
            possible_home.append(now_home)
#print(mid, possible_home)
if len(set(possible_home))>=c:
    l=mid+1; answer=mid # 정답 후보군 (매번 갱신예정)
else :
    r=mid-1

print(answer)

### <반성 점>
- 처음에 무리하게 while 문으로 돌린 것, 
- 그리고 코드 깔끔성을 위해 ; 로 한 줄에 쓸 때 for문이랑 sort()는 한 줄에 쓰지 마라
### <배운 점>
# Parametric Search?
> ## 최적화 문제를 결정문제로 바꾸어 풀이하는 방법 
- 이 문제에 적용해보면

#### 가장 인접한 두 공유기 사이 거리를 최대로 하는 문제(최적화)
를 아래로 변경하는 것
#### 거리 d가 주어졌을 때 공유기 사이의 거리를 d 이상으로 하면서 c개의 공유기 설치 가능한 지 결정하는 문제