[Python 3] BOJ - 2539 "모자이크"

 # 문제 링크

https://www.acmicpc.net/problem/2539

2539번: 모자이크

 

# 풀이

 개인적으로 생각했을 때 이 문제의 핵심은 이분탐색이라고 생각한다. 왜냐하면 문제의 조건에 맞게 Xcm로 모든 칸들을 덮을 수 있다고 하자. 그렇다면, (X+ 1)cm로 모든 칸들을 덮을 수 있는가? 그렇다. 그렇다면, (X + 2)cm로 모든 칸들을 덮을 수 있는가? 그렇다. 반대로, 문제의 조건에 맞게 Xcm로 모든 칸들을 덮을 수 없다고 하자. 그렇다면, (X - 1)cm로 모든 칸들을 덮을 수 있는가? 그렇지 않다. 역시 (X + 2)cm로도 덮을 수 없다. 

따라서, 어떤 특정한 길이가 가능하다면, 굳이 그 길이보다 긴 길이는 탐색할 필요가 없고, 반대의 경우도 굳이 그 길이보다 짧은 길이는 탐색할 필요가 없기 때문에 이분 탐색을 통해 효율적인 탐색이 가능하다

 그렇다면 현재 길이로 모든 칸들을 덮을 수 있는지 어떻게 판단해야 할까? 종이는 무조건 밑변에 접해서 붙여야 한다는 조건을 활용하여 하나도 겹치지 않게 할 수 있지 않을까?

<그림 1. 4 X 12인 경우 반례>

 위 그림 1에서 반례가 성립함을 알 수 있다. 왜냐하면 겹치지 않게 한다고 해서 최적의 종이 갯수를 찾을 수 없기 때문이다. 그림에서 보듯 아무런 칸이 없는 종이가 있을 수 있기 때문이다. 따라서, 이 경우 3cm로 한다면 4개가 아닌 더 작은 갯수인 3개로도 가능하다. 그렇다면 각 색종이당 최소 하나의 칸이 있으면 이런 경우를 방지할 수 있다.

 그런데 항상 색종이를 밑변에 붙여야 하기 때문에 높이가 정해진다 해도 사실상 색종이는 x좌표를 기준으로 좌우로 움직여야 한다. 따라서, 각 칸들을 x좌표 기준으로 정렬 후, 가장 왼쪽 칸부터 색종이의 시작으로 정하고 색종이를 붙여 나간다. 결국 왼쪽에서 시작해서 현재 길이의 색종이를 벗어나는 최초의 x좌표가 새로운 색종이의 시작이 되어야 필요한 색종이의 갯수가 최소가 된다

<그림 2 4 x 3에서의 반례>

 위 그림에서 오른쪽의 경우, 가장 왼쪽에서 시작하지 않았기 때문에 부득이 하게 색종이가 하나 더 필요하다. 따라서, 귀류법을 통해 그리디한 선택이 최적에 도달한다는 것이 증명되었으므로, 이분 탐색을 하기 전 x축 기준으로 정렬이 필요함을 알 수 있다

 또한 주의해야 할 점이 하나가 더 있는데, 일반적인 이분 탐색에서 left 혹은 low값이 0이어도 정답을 구하는데 문제가 없는 경우가 많으나, 이번 문제는 반드시 left(low)값이 칸들의 최대 높이가 되어야 한다는 점이다. 상식적으로 생각했을 때, 어떠한 색종이라도 밑변에 붙어야 하므로 칸들의 최대 높이보다 작다면 무슨 짓을 하든 가장 높은 칸을 색종이로 덮을 수 없다는 것은 자명하다. 따라서 이 점을 주의하면 정답을 구할 수 있다

 

 # 코드

import sys

# 입력부
n, m = map(int, sys.stdin.readline().split())
k = int(sys.stdin.readline())
q = int(sys.stdin.readline())
arr = []
left = 0
right = 9876543210
for _ in range(q):
    a, b = map(int, sys.stdin.readline().split())
    
    # 최소 높이 갱신
    left = max(left, a)
    arr.append((a, b))
    
# x축 기준 정렬
arr.sort(key=lambda x : (x[1]))

while left < right:
    # 이 때 mid 값이 색종이의 길이가 된다
    mid = (left + right) // 2
    
    # idx : 현재 새로운 색종이의 시작하는 칸의 인덱스
    idx = 0
    
    # cnt : 현재까지 몇개의 색종이를 붙였는가에 대한 변수
    cnt = 0
    while idx < q:
        cnt += 1
        start_x = arr[idx][1]
        
        # 문제 조건에 의해 색종이는 반드시 밑변에 붙어야 하므로 start_y는 1
        start_y = 1
        i = idx
        
        # 현재 색종이로 덮을 수 있는 칸을 탐색
        while i < q and start_x <= arr[i][1] < start_x + mid and start_y <= arr[i][0] < start_y + mid:
            i += 1
            
        # 현재 색종이로 덮을 수 없는 최초의 칸이 다시 시작점이 된다
        idx = i
        
    # 만일 현재 mid 길이로 k개 이하로 덮을 수 있다면, 길이를 줄인다
    if cnt <= k:
        right = mid
    # 그렇지 않으면 길이를 늘린다
    else:
        left = mid + 1
        
# 정답 출력
print(right)