백준 2539 - 모자이크

문제 설명

입출력 및 제한사항

풀이

문제 요약은 다음과 같다. n × m 도화지에 잘못 칠해진 칸의 좌표가 주어진다. 한 변 길이가 같은 정사각형 색종이를 최대 k장 사용할 수 있고, 색종이는 도화지의 아래 변에 붙여서 사용한다. 모든 잘못 칠해진 칸을 가릴 수 있도록 할 때, 필요한 색종이의 최소 한 변 길이 s를 구하는 문제이다.

 

항상 도화지의 아래 변에 붙여서 사용하기 때문에 y 좌표는 생각하지 않아도 된다. 아래 붙여서 사용했을 때 x축에서 가장 멀리 떨어져있는 y좌표의 값만 넘긴다면 x 좌표만 생각하면 된다.

 

뭔가 이분 탐색하기엔 범위가 너무 좁아서 긴가민가했는데 다른 효율적인 풀이가 마땅히 생각나지 않아 이분 탐색으로 풀이했다. 탐색 조건은 종이의 크기이고 중앙값이 모든 좌표를 커버한다면 종이가 더 작아도 되므로 right = mid, 커버하지 못한다면 종이가 더 커야하므로 left = mid로 조건을 주었다.

내 코드

import sys
input = sys.stdin.readline
mis = lambda: map(int, input().split())
INF = float('inf')

n, m = mis()
paper_cnt = int(input())
miss_cnt = int(input())
coor = [[*mis()] for _ in range(miss_cnt)]

min_size = max(coor, key= lambda x: x[0])[0]
x_coor = sorted({i[1] for i in coor})

def check(s, coor):
    if s < min_size:
        return False
    
    used = 0
    i = 0
    n = len(coor)
    while i < n:
        used += 1
        cover_to = coor[i] + s - 1
        
        while i < n and coor[i] <= cover_to:
            i += 1
        
        if used > paper_cnt:
            return False

    return True

left = 0
right = 1000001
while left + 1 < right:
    mid = (left + right) // 2
    
    if check(mid, x_coor):
        right = mid
    else:
        left = mid
print(right)

이분탐색의 로직은 위에서 설명한 그대로이고, 커버할 수 있는지 판별하는 check 함수는 그리디하게 구성했다.

아직 덮지 않은 가장 왼쪽 열 x를 잡고, 색종이 1장을 [x, x+s-1] 범위로 깔고 이 구간에 포함되는 열들은 모두 건너뛴다. 이 과정을 반복해서 사용한 장수가 k를 초과하면 실패, 끝까지 덮으면 성공으로 판별한다.

 

사실 min_size부터 시작한다면 check 함수 내부에서 min_size 판별을 굳이 안해도 되지만 이분탐색 범위를 넉넉하게 잡는 습관이 들다보니,,, ㅎㅎ

 

시간 복잡도

이분탐색: O(logN)

check(): O(n) (중복이 제거되어서 실제론 n보다 작음)

따라서 총 시간 복잡도는 O(n logN)

고찰

만약 도화지의 아래에 붙여서 사용한다는 조건이 없다면 어떻게 풀이해야 할까? 이제는 1차원이 아니라 2차원에서 최적을 판단해야한다. 기존처럼 이분탐색으로 풀이가 가능할 것 같은데, check 함수를 올바르게 수정해야한다. 

 

아직 덮이지 않은 가장 왼쪽 아래의 점 p를 하나 잡고, p를 꼭짓점으로 덮는 정사각형의 위치만 재귀로 탐색하는 아이디어를 생각해볼 수 있을 것 같다. 완전탐색 비슷하게!