[Python][백준 6209][이분 탐색] 제자리 멀리뛰기 - 컴도리돌이

반응형

6209번: 제자리 멀리뛰기

---

풀이 과정

해당 문제는 저어어어어엉말 어려웠다..  👏👏 해당 문제의 알고리즘 분류는 이분 탐색으로 표기되어 있었고, 그것은 나에게 도움이 되지 않았다...😂😂  결국 이분 탐색의 target을 바위 간에 거리로 잡아야 하는데, 바위를 제거를 어떤 식으로 구현해야 할지 감이 잡히지 않아서 매우 고생했던 문제였다..

 

1. 입력받은 돌섬(rocks)들의 거리를 오름차순 정렬을 하고, 주어진 거리도 rocks에 append 해주자.

2. 결국 돌섬의 거리의 최소 값을 target으로 잡아야 한다. 그러므로 left = 0, right = 탈출 거리로 잡았다.

3. 이분 탐색

• 여기서 mid는 현재 위치와 바위와의 거리로 두었다. prev는 현재 위치하고 있는 돌섬의 거리이고, cnt는 제거한 돌섬의 수이다. 현재 위치는 항상 0으로 시작한다.
• 3-1)  rock - prev < mid : 현재 위치에서 돌섬의 거리가 mid 보다 작다면, 모두 제거한다.
• 3-2)  rock - prev >= mid : 현재 위치에서 돌섬의 거리가 mid와 같거나 크면, 현재 위치를 해당 바위로 옮겨 준다.
• 3-3) cnt <= m : 현재 제거한 돌섬의 수가 m보다 적으면 left 값을 mid + 1로 잡고 해당 출력 값(ans)을 mid로 업데이트해주었다. 그 반대일 경우 돌섬을 너무 제거했기 때문에 right를 mid - 1로 잡아서 제거한 수를 줄인다.

---

풀이 코드

import sys; input = sys.stdin.readline
d,n,m = map(int,input().split()) 
rocks = sorted([int(input()) for _ in range(n)]) + [d]
left,right,ans = 0,d,0
while left <= right :
  mid,prev,cnt = (left+right)//2,0,0  # 바위와 현재 위치 사이의 거리, 현재 위치, 바위를 제거한 개수
  for rock in rocks : # 거리 재기
    if rock - prev < mid : cnt += 1 #바위와 현재 위치 사이의 거리가 mid 보다 짧으면 제거
    else : prev = rock # 현재 위치를 해당 바위로 옮김
  if cnt <= m : left,ans = mid+1,mid # 제거한 바위가 m보다 작거나 같을 경우 left, ans 업데이트
  else : right = mid - 1 #많을 경우 mid를 줄여서 바위를 조금 제거.
print(ans)