[BOJ] 2539 - 모자이크 (Python)

 

 

아이디어

 

이분 탐색으로 잘못 칠해진 칸을 모두 가릴 수 있는 가장 작은 색종이 크기를 구한다.

 

 

풀이

 

모든 색종이는 반드시 도화지 밑변에 맞추어 붙이므로 색종이 크기는 잘못 칠해진 칸 행의 최댓값부터 시작한다.

 

import sys

input = sys.stdin.readline

def solution():
    R, C = map(int, input().split())
    N = int(input())
    M = int(input())
    wrong = []
    s = 0
    for _ in range(M):
        r, c = map(int, input().split())
        wrong.append(c)
        if s < r:
            s = r
    wrong.sort()
    e = max(s, R, C)
    while s <= e:
        m = (s+e)//2
        last = cnt = 0
        for c in wrong:
            if c > last:
                last = c+m-1
                cnt += 1
                if cnt > N:
                    s = m+1
                    break
        else:
            e = m-1
    print(s)

solution()