[Python][백준 2539][이분 탐색] 모자이크 - 컴도리돌이

반응형

2539번: 모자이크

---

풀이 과정

이분 탐색의 팁은 주체를 찾고 해당 주체를 target으로 잡아서 이분 탐색을 해주면 된다. 하지만 해당 문제를 3번이나 틀렸다.😂

 

1. 첫째줄부터 셋째 줄까지 입력을 받고 잘못 칠해진 칸(y, x) 값을 입력받을 때 높이(y)의 max 값을 left에 저장해줘야 한다... 해당 작업을 하지 않고 정형적인 이분 탐색의 left 값을 0으로 해놓아서 9%에서 바로 틀려버렸다 ㅠ 색종이는 밑변에 맞춰서 붙이기 때문에 최소한 가장 높은 높이의 색종이 칸을 가지고 있어야 한다.

 

2. 그 이후에는 사실 높이 값은 중요하지 않다. binarySearch 함수에서도 x 값을 기준으로만 색종이 수를 업데이트해주었다. 이분 탐색하기 전에 잘못 칠해진 좌표를 밑변(x) 기준으로 정렬시켜줘야 한다!!

 

3. 이분 탐색 left = 높이의 최대 값, right = 밑변의 최대 값(문제에서는 10^7으로 잡아서 필자도 10^7으로 잡았다.)

• 3-1) xx 변수는 잘못 색칠한 좌표 배열의 첫 번째 인덱스의 x 값으로 초기화해준다.
• 3-2) 초기 값 xx에 색종이의 길이(p)를 더한 xx+p 이 현재 밑변의 길이(x) 보다 클 경우 현재 색종이의 길이로 현재 밑변을 가릴 수 없기 때문에 색종이 수를 카운터(+1)해주고 초기 값 xx를 x로 업데이트해준다.
• 3-3) 반환된 색종이의 수가 사용할 수 있는 색종이의 수(paper) 보다 작거나 같을 경우 출력 값을 mid로 업데이트해주고, right를 mid-1을 해준다. 그 반대면 left를 mid+1로 업데이트해준다.

---

풀이 코드

import sys; input = sys.stdin.readline
r,c = map(int,input().split())
paper = int(input()) 
wrongPaper = []
left,right,ans = 0,10 ** 7 ,0

for _ in range(int(input())) :
  y,x = map(int,input().split())
  left = max(left,y)
  wrongPaper.append((x,y))

wrongPaper.sort()

def binarySearch(p) :
  xx = wrongPaper[0][0]
  cnt = 1
  for x,y in wrongPaper :
    if x >= xx + p :
      cnt += 1
      xx = x
  return cnt
while left <= right :
  mid = (left+right)// 2  # 한변의 길이
  if binarySearch(mid) <= paper :
    ans = mid
    right = mid - 1
  else :
    left = mid + 1

print(ans)