[백준/파이썬, 코틀린] 14658번 하늘에서 별똥별이 빗발친다

문제 주소

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

14658번: 하늘에서 별똥별이 빗발친다

문제 해석

문제 풀이

단순히 n, m을 통해 그려서 풀기에는 너무 큰 입력 범위이다. 따라서 모든 범위를 완전 탐색해서 구할 수는 없다.

떨어지는 별똥별의 입력 범위는 1 <= 100이므로 이 값을 최대한 활용해서 해결해야 한다.

 

두 별똥별이 떨어질 때 만들어질 수 있는 가장 큰 사각형 범위는 두 별똥별이 경계에 위치해 있을 때다. 이를 사각형으로 그려보면 두 별똥별의 최소 x, y 값을 시작으로 할 때 가장 큰 사각형 범위가 그려진다.

해당 사각형 시작 좌표와 그릴 수 있는 최대 크기인 l까지의 사각형을 그려 포함되는 별똥별들을 찾아나가면 n^3 (n = 100)의 시간복잡도로 문제를 해결해 나갈 수 있다.

문제 코드

Python

import sys


def solve(n, m, l, k, arr):
    answer = 0
    for i in range(k):
        for j in range(k):
            cnt = 0

            # 두 별을 걸치는 가장 왼쪽 상단 좌표
            sx, sy = min(arr[i][0], arr[j][0]), min(arr[i][1], arr[j][1])

            for x, y in arr:
                # 구한 좌표의 최대 범위 별 개수 구하기
                if sx <= x <= sx + l and sy <= y <= sy + l:
                    cnt += 1
            answer = max(answer, cnt)

    return k - answer


def main():
    n, m, l, k = map(int, input().split())
    arr = []
    for _ in range(k):
        arr.append(list(map(int, input().split())))
    print(solve(n, m, l, k, arr))


if __name__ == '__main__':
    sys.setrecursionlimit(10 ** 5)
    input = sys.stdin.readline
    main()

---

Kotlin

import java.io.BufferedWriter
import java.io.OutputStreamWriter

fun main() = with(System.`in`.bufferedReader()) {
    val sout = BufferedWriter(OutputStreamWriter(System.out))

    var line = readLine().split(" ").map { it.toInt() }
    var l = line[2]
    var k = line[3]

    var arr = Array(k) {
        readLine().split(" ").map { it.toInt() }
    }

    sout.appendLine(solve(l, k, arr))
    sout.close()
}

fun solve(l: Int, k: Int, arr: Array<List<Int>>): String {
    var count = 0

    for (star1 in arr) {
        for (star2 in arr) {
            var sx = minOf(star1[0], star2[0])
            var sy = minOf(star1[1], star2[1])
            var cnt = 0

            for (star in arr) {
                if (sx <= star[0] && star[0] <= sx + l &&
                    sy <= star[1] && star[1] <= sy + l
                ) {
                    cnt += 1
                }
            }
            count = maxOf(count, cnt)
        }
    }

    return (k - count).toString()
}

 

제출 결과