[파이썬] 백준 2539 : 모자이크 (골드3)

[파이썬] 백준 2539 : 모자이크 (골드3)

 

2539번: 모자이크

---

문제

---

풀이

0. 방향성 생각

y좌표 최대값이 탐색 시 최소 종이 사이즈

그 이후로는 x좌표에 잘못칠한 칸이 있는지만 확인

 

1. 입력

import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
paper = int(input())
error = set()
min_size = 0

for _ in range(int(input())):
    y,x = map(int,input().split())
    if y >= min_size:
        min_size = y # 높이 y까지는 닿아야함 최소사이즈
    error.add(x)

error에 x좌표들을 모두 넣고

최대 y값을 min_size로 반환한다.

2. 탐색

error = list(error)
error.sort()

while True:
    memory = error[0]
    count = 1
    fail = False
    for loc in error:
        if loc >= memory + min_size: # 다음 종이 사용할 때
            memory = loc # 시작 위치 업데이트
            count += 1 # 종이 수 +1
        if count > paper: # 사용 개수 넘어가면
            fail = True # 실패
            break

    if not fail: # 실패 안한 케이스 찾으면
        print(min_size) # 출력
        break
    min_size += 1

잘못 칠한 칸을 정렬한다.

이후 좌표 x에서 현재 종이 크기인 min_size를 붙이면 x+min_size-1 까지는 붙이고

x+min_size부터는 새로운 종이를 붙인다. 이 때 종이 개수를 늘리고 시작 위치를 업데이트해준다.

 

사용 개수 paper를 넘어가면 실패, min_size += 1로 크기 늘려주기

실패하지 않았으면 출력

 

---

전체코드

import sys
input = lambda : sys.stdin.readline().rstrip()

h,w = map(int,input().split())
paper = int(input())
error = set()
min_size = 0

for _ in range(int(input())):
    y,x = map(int,input().split())
    if y >= min_size:
        min_size = y
    error.add(x)

error = list(error)
error.sort()

while True:
    memory = error[0]
    count = 1
    fail = False
    for loc in error:
        if loc >= memory + min_size:
            memory = loc
            count += 1
        if count > paper:
            fail = True
            break

    if not fail:
        print(min_size)
        break
    min_size += 1

코멘트

원래대로면 그냥 이진탐색으로 푸는게 맞는데 데이터 사이즈가 1000개 이하 (중복 발생할 수 있는 점에서 더 작음),

최소사이즈부터 출력하는거라 그냥 해도 맞을거같아서 정렬하고 +1씩 해주면서 풀었음.