[백준/2539] 모자이크 (Python)

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

2539번: 모자이크

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:15:56

 

---

 

문제 설명

 

수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 정사각형 모양의 칸을 만들고, 각 칸마다 같은 색의 물감으로 색칠을 하였다. 그런데 잘못 칠해진 칸이 있음을 발견하게 되었다.

수찬이는 도화지와 색깔이 같은 색종이를 사서 잘못 칠해진 칸에 색종이를 붙이고 다시 그리는 것이 좋겠다고 생각하고 선생님께 상의를 드렸다. 선생님께서는 정해진 장수의 색종이를 사용하여 아래와 같은 조건을 따르면서 잘못 칠해진 칸을 모두 가리되, 가장 작은 색종이의 크기를 구하는 새로운 문제를 내셨다.

1. 사용되는 색종이는 모두 크기가 같고 정사각형 모양이다.
2. 색종이 크기는 한 변의 길이로 나타내며, 원하는 크기의 색종이는 모두 구할 수 있다.
3. 모든 색종이는 반드시 도화지의 밑변에 맞추어 붙인다. 이때 색종이를 겹쳐서 붙일 수 있다.

 

도화지 위의 칸은 행 번호와 열 번호로 나타낸다. 예를 들어 위 그림에서 가장 왼쪽에 있는 잘못 칠해진 칸 A의 위치는 (2, 1)이다. 위 그림과 같이 도화지에서 잘못 칠해진 칸이 9개 주어지고 색종이 4장을 사용한다면 가장 작은 색종이의 크기는 3cm이다.

 

도화지의 행의 개수와 열의 개수, 그리고 도화지에 잘못 칠해진 칸들의 위치가 주어질 때, 주어진 장수의 색종이를 사용하여 앞의 세 가지 조건에 따라 모든 잘못 칠해진 칸을 가릴 수 있는 가장 작은 색종이의 크기를 구하는 프로그램을 작성하시오.

 

입력 및 출력

 

입력

첫째 줄에는 도화지 위의 행의 개수와 열의 개수를 나타내는 자연수가 빈칸을 사이에 두고 주어진다. 행의 개수와 열의 개수는 모두 1000000 이하이다. 둘째 줄에는 사용할 색종이의 장수를 나타내는 자연수가 주어진다. 사용할 색종이는 100장 이하이다. 셋째 줄에는 도화지에 잘못 칠해진 칸의 개수를 나타내는 자연수가 주어진다. 잘못 칠해진 칸은 1000개 이하이다. 넷째 줄부터 마지막 줄까지 잘못 칠해진 칸의 위치가 한 줄에 하나씩 주어진다. 잘못 칠해진 칸의 위치는 빈칸을 사이에 두고 행 번호가 주어진 다음 열 번호가 주어진다.

 

출력

첫째 줄에 주어진 장수의 색종이를 사용하여 잘못 칠해진 칸을 모두 가릴 수 있는 가장 작은 색종이의 크기가 몇 cm인지를 나타내는 자연수를 출력한다.

 

입력 예시

4 14
4
9
1 2
2 1
2 3
1 6
3 5
1 10
3 6
1 12
2 13

 

출력 예시

3

 

 

---

 

풀이

 

이분 탐색 문제. 색종이를 겹칠 수 있으므로, 필요한 최소 색종이 이하기만 하면 무조건 모든 모자이크를 덮을 수 있다. (남은 색종이는 기존 색종이에 겹쳐버리면 된다!)

 

또한, 가장 높은(즉 row가 제일 큰) 좌표를 기준으로 start 값을 잡아야 한다. 그렇지 않으면 색종이의 높이가 낮아 덮지 못하는 경우가 생겨나기 때문이다. 주어진 맵의 최대 좌표인 R를 end로 잡을 수 있겠다. 좌표의 개수를 N이라고 한다면, 한 번의 탐색에 O(N), 그리고 전체 이분 탐색에 O(NlogN)이 소요되므로 충분히 제한 시간 내에 확인 가능하다.

 

• init : N개의 모든 좌표를 입력받는다. 우리가 필요한 핵심 좌표는 col이므로 그 값을 리스트에 저장하고, 앞서 말한 대로 가장 큰 row값을 찾는다. 그리고 col_list는 정렬하도록 한다(순차적으로 탐색하기 위함이다). col_list와 max_row를 반환한다.
• cal_paper_num : col_list를 순회하며 정해진 변의 길이 sz의 색종이로 덮기 위해 필요한 최소 개수를 구한다.
• binary_search : 주어진 start에서부터 end까지 이분 탐색을 진행하는 함수이다. 중간값인 mid를 색종이의 한 변의 길이로 잡고 cal_paper_num을 호출하여 모두 덮는데 필요한 색종이의 개수를 구한다. 그리고 개수가 주어진 개수 이하인지 아닌지에 따라 start와 end를 조정하도록 한다.
• solve : 메인함수. init 함수를 통해 start, end값 및 col_list를 얻고, 이를 binary_search에 전달하여 정답을 출력한다.

 

풀이 코드

R, C = map(int, input().split())
needed_paper = int(input())
N = int(input())

def init() :
  max_row = 0
  col_list = list()
  for _ in range(N) :
    r, c = map(int, input().split())
    max_row = max(r, max_row)
    col_list.append(c)

  col_list.sort()
  return max_row, col_list

def cal_paper_num(col_list, sz) :
  result = 1
  prev = col_list[0]-1
  if len(col_list) > 1 :
    for c in col_list :
      if prev + sz < c :
        result += 1
        prev = c-1

  return result

def binary_search(start, end, col_list) :
  result = end
  while start <= end :
    mid = (start + end) // 2
    used_paper = cal_paper_num(col_list, mid)
    if used_paper <= needed_paper :
      result = min(result, mid)
      end = mid - 1
    else :
      start = mid + 1

  return result

def solve() :
  max_row, col_list = init()
  start, end = max_row, R
  result = binary_search(start, end, col_list)
  print(result)

solve()

풀이 완료!