2539. 모자이크 (Python, Swift)

2539번: 모자이크

 

풀이

 문제의 조건을 잘 읽어봐야 된다..........

 

 문제에 주어진 조건 중에서 모든 색종이는 반드시 도화지의 밑변에 맞추어 붙인다고 되어있다. 처음에 이걸 도화지의 모든 행의 밑변으로 이해하고 풀었는데 결국 해결하지 못하여 인터넷에 검색해서 풀이를 조금 봤는데 알고보니 가장 아래 밑변 하나를 의미하는 거였다. 이걸 알고나니 쉽게 문제를 해결할 수 있었다ㅎ.

 

 문제에서 가장 작은 색종이의 크기를 물어보고 있다. 색종이의 크기가 N이고 N크기의 색종이로 잘못 칠한 칸을 주어진 색종이의 개수로 모두 가릴 수 있다고 가정해보자. 그럼 N+1, N+2, ....와 같이 N보다 크기가 큰 색종이는 가릴 수 있을까? 당연히 가릴 수 있다. 그럼 N-1, N-2, .....와 같이 N보다 작은 크기를 가진 색종이는? 이건 다시  한 번 탐색을 해봐야 한다. 즉, 우리는 이분 탐색을 사용하여 가장 작은 크기의 색종이를 구할 수 있음을 알 수 있다.

 

 범위를 설정할 때 하나 생각할 것이 있다. 보통 이분 탐색을 할 때 left는 0으로 잡는데 이번 문제에서는 조금 다르게 설정한다. 위에서 말했 듯이 색종이는 도화지의 밑변에 맞추어 붙인다. 잘못 칠한 칸이 (5, 2)에 있다고 가정해보자. 이 때 크기가 4인 색종이로 저 칸을 가릴 수 있을까? 가릴 수 없다. 그렇기 때문에 색종이는 최소한 가장 높이 있는 잘못 칠한 칸의 행에 해당하는 높이를 가지고 있어야 한다. left는 입력 받는 행 중 가장 큰 행으로 설정해 주면 된다.

 

 크기가 N인 색종이 몇 장으로 잘못 칠한 칸을 가릴 수 있는지 알아보는 방법은 열을 기준으로 가장 왼쪽부터 색종이를 붙이는 것이다. 입력으로 받은 잘못 칠한 칸을 열을 기준으로 오름차순 정렬한다. 행의 경우 위에서 left를 통해 최소한의 높이를 구했으므로 행은 신경 쓰지 않고 열만 보면 되는 것이다. 크기가 N인 색종이 한 장으로 (현재 열 ~ 현재 열 + N - 1)까지 있는 잘못 칠한 칸을 가릴 수 있다. 이렇게 열을 기준으로 앞에서 부터 탐색하며 총 몇 장의 색종이가 필요한지를 구하면 된다.

 

 하나 주의할 건 파이썬은 괜찮은데 swift로 풀 때는 런타임 에러가 발생한다. 문제의 질문 게시판에서 답을 알 수 있었는데 입력의 어딘가에서 공백이 포함된 값이 입력으로 주어지고 있다고 한다. 그래서 입력을 받을 때 공백을 제거해 주어야 한다. 개빡치는 문제😡

 

코드

[Python]

import sys
input = sys.stdin.readline


# 열을 기준으로 앞에서 부터 붙여나가며 색종이의 개수를 하나씩 늘려준다.
# length: 색종이의 크기 
def solve(length):
    start = coord[0][0]
    count = 1
    for (y, _) in coord:
        # 다음 열이 start열부터 시작하여 붙인 색종이로 가릴 수 없으면
        # start를 다음 열로 새롭게 설정하고 색종이를 하나 더 붙인다
        if y >= start + length:
            start = y
            count += 1

    return count


if __name__ == '__main__':
    R, C = map(int, input().split())  # 도화지 행의 개수, 열의 개수
    paper = int(input())  # 사용할 색종이 장 수
    fault = int(input())  # 잘못 칠해진 칸의 개수
    coord = []
    maxHeight = 0

    for _ in range(fault):
        a, b = map(int, input().split())  # 행, 열
        maxHeight = max(maxHeight, a)
        coord.append((b, a))

    coord.sort() # 열을 기준으로 정렬 
    left = maxHeight # 색종이는 최소 maxHeight의 높이를 가져야 한다.
    right = 1_000_001
    res = 0

    while left <= right:
        mid = (left + right) // 2

        if solve(mid) <= paper:
            res = mid
            right = mid - 1
        else:
            left = mid + 1

    print(res)

 

[Swift]

import Foundation
typealias coordElement = (col: Int, row: Int)

// 열을 기준으로 앞에서 부터 붙여나가며 색종이의 개수를 하나씩 늘려준다.
// length: 색종이의 크기
func solve(_ length: Int) -> Int {
    var start: Int = coord[0].col
    var count: Int = 1
    
    for (y, _) in coord {
        // 다음 열이 start열부터 시작하여 붙인 색종이로 가릴 수 없으면
        // start를 다음 열로 새롭게 설정하고 색종이를 하나 더 붙인다
        if y >= start + length {
            start = y
            count += 1
        }
    }
    
    return count
}


var R: Int = 0 // 도화지 행의 개수
var C: Int = 0 // 도화지 열의 개수

if let input = readLine() {
    let inputs = input.trimmingCharacters(in: .whitespaces).split(separator: " ").map { Int($0)! }
    
    R = inputs[0]
    C = inputs[1]
}

var paper: Int = 0 // 사용할 색종이 장 수
if let input = readLine() {
    paper = Int(input.trimmingCharacters(in: .whitespaces))!
}

var fault: Int = 0 // 잘못 칠해진 칸의 개수
if let input = readLine() {
    fault = Int(input.trimmingCharacters(in: .whitespaces))!
}

var coord: [coordElement] = []
var maxHeight: Int = 0

for _ in 0..<fault {
    var a: Int = 0
    var b: Int = 0
    
    if let input = readLine() {
        let inputs = input.trimmingCharacters(in: .whitespaces).split(separator: " ").map { Int($0)! }
        
        a = inputs[0]
        b = inputs[1]
    }
    
    maxHeight = max(maxHeight, a)
    coord.append((b, a))
}

coord.sort { $0.col < $1.col } // 열을 기준으로 정렬

var left: Int = maxHeight // 색종이는 최소 maxHeight의 높이를 가져야 한다.
var right: Int = 1_000_001
var res: Int = 0

while left <= right {
    let mid: Int = (left + right) / 2
    
    if solve(mid) <= paper {
        res = mid
        right = mid - 1
    } else {
        left = mid + 1
    }
}

print(res)