[백준] 2110번 공유기 설치

why...

 

www.acmicpc.net/problem/2110

2110번: 공유기 설치

왜...

이거 진짜 문제를 이해하는데만.. 한참 걸린듯ㅠㅠ 자괴감들어요........ 이분탐색 너무 어려워...

시작조차 하지못하고 고민만 너무 오래해서 결국 구글의 힘을 빌렸고.. 먼저 풀어보신 분들 존경하고 감사합니다😭

 

처음에는 가장 첫 집, 끝집에 무조건 공유기를 놓고 가운데를 어떻게 옮겨야 하나 고민을 했는데

좀더 내가 풀어볼만한? 코드로 짜볼만한? 설명을 하나 읽어서 그걸 토대로 다시 고민

---

중요했던 것

• 집은 중복된 좌표가 없으므로 집과 집 사이의 최소 간격은 무조건 1 이다!!! (s = 1)
• 집~집 사이의 최대 간격은 첫집~끝집  (e = house[-1] - house[0])
• 그래서 집과 집 사이의 간격(dist)를 최소(s)와 최대(e) 사이에서 왔다갔다 하면서 적당한 값을 찾는것이 목표.

 

코드 이전에 실행화면 먼저!

나는 dist = 4칸 이상씩 떨어뜨려서 공유기를 설치하고싶다

그래서 첫집(A)에는 무조건 공유기를 일단 설치하고(cnt = 1), 4칸씩 가면서 공유기를 달 수 있는지 확인할것이다.

for문을 돌면서 각 집마다 확인을 한다.

• B는 1칸밖에 차이가 안나서 안됨
• C도 3칸 떨어져서 안됨 
• D는 7칸 떨어져있어서 합격! 공유기 하나 설치! cnt = 2 하고, 이제는 D를 기준으로 4칸 떨어진 다음 집을 찾고싶다
• E는 D와 1칸 떨어져있기때문에 안됨

그렇게 모든 집을 다 돌아서 공유기를 총 2개 설치한게 위의 경우이다. 3개 설치하고싶었는데 너무 적다. 

 

공유기가 너무 적게 설치된걸 보니 거리가 너무 듬성듬성 했던것같아서 거리를 줄이게 됐다 (e = c - 1)

dist 를 계산하면 2가 나온다.

A에 공유기를 심어서 cnt = 1

• A~B는 1칸이라 실패
• A~C는 3칸이라 성공 cnt = 2
• C~D는 4칸이라 성공 cnt = 3
• D~E는 1칸이라 실패

총 cnt = 3으로 내가 원하는만큼 공유기를 설치하기는 했지만

 

간격을 좀 키워보기로 하여 s = c + 1 로 변경. dist = 3이 됐다

A에 공유기 심어서 cnt = 1

• A~B는 거리 1로 실패
• A~C는 거리 3으로 성공 cnt = 2
• C~D는 거리 4로 성공 cnt = 3
• D~E는 거리 1 실패

공유기 3개를 심었는데, dist는 3이 되므로 이게 답이 됨... 

 

---

🏃‍♀️작성한 코드

# 2110 번 : 공유기 설치
def binary_search_2110():
  # n, c = map(int, input().split())
  # house = []
  # for _ in range(n):
  #   house.append(int(input())) #집의 좌표를 입력받음

  n = 5
  c = 3
  house = [1,2,8,4,9]

  house.sort() #1,2,4,8,9

  e = house[-1] - house[0] #첫집에서 끝집까지의 거리 : 간격중 최대 간격
  s = 1 #간격중 최소간격 (최소간격이 될수있는건 1임. 중복 좌표가 없다고 했으니 0 불가) 


  while s <= e :
    cnt = 0
    dist = (e+s) // 2 #공유기를 설치하기위해 각재는 거리
    print('dist-------------------------------------', dist)
  
    prev_house = house[0]
    cnt += 1 #맨 첫집에 공유기 하나 설치
    print('cnt ---', cnt)

    for i in range(1, len(house)):
      print('---------------------------i ', i)
      tmp_house = house[i]
      d = tmp_house - prev_house #두 집 사이의 거리
      print('tmp_house...', tmp_house, '// d...' ,d)
      
      if d >= dist :
        cnt += 1
        prev_house = tmp_house
        print('cnt ---', cnt)
      else :
        continue

    if cnt < c : #설치한 공유기가 모자르다면(간격이 너무 넓어서)
      e = dist - 1 #거리를 줄이자
    else : #공유기가 딱맞거나 or 너무많이 설치됐다면 (간격이 촘촘해서) 
      s = dist + 1 #거리를 늘리자
      answer = dist
  print(answer)