[백준] #14658 하늘에서 별똥별이 빗발친다(python)

수영·2023년 1월 5일

Python3 백준

백준

목록 보기

100/117

📌문제

“오빠! 나 얼마만큼 사랑해?”

“널 위해서라면 저기 저 하늘의 별이라도 따다 줄 수 있어. 지금 따줄까?”

“에이, 거짓말!”

“정말이야. 한 번 봐봐!”

욱제는 하늘을 발로 차버렸다. 그랬더니 정말 별이 떨어졌다. 그런데, 정말로 별이 지구로 떨어지기 시작했다. 욱제는 지구를 지키는 정의의 용사가 되기로 결심했다.

“자기야, 나 세계를 지키고 올게. 꼭 돌아올 테니 조금만 기다려줘.”

지구의 파괴를 막기 위해서는 지표면에 떨어지는 별똥별의 수를 최소화해야 한다. 욱제는 커다란 네모난 L*L 크기의 트램펄린을 준비했다. 별똥별이 어디로 떨어질지는 이미 알고 있기 때문에, 욱제는 이 트램펄린으로 최대한 많은 별똥별을 우주로 튕겨낼 계획이다. 하지만 학교 예산으로 트램펄린을 구매하는 욱제는 이 긴급한 와중에도 예산 심의 통과를 기다리느라 바쁘다!

욱제를 도와 세계를 구하자. 최대한 많은 별똥별을 튕겨내도록 트램펄린을 배치했을 때, 지구에는 몇 개의 별똥별이 부딪히게 될까? (별똥별이 떨어지는 위치는 겹치지 않으며 별똥별은 트램펄린의 모서리에 부딪혀도 튕겨나간다!) 트램펄린은 비스듬하게 배치 할 수 없다.

입력

첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 뜻한다. 이후 K개의 줄에 걸쳐 별똥별이 떨어지는 위치의 좌표 (x, y)가 주어진다. (0 ≤ x ≤ N, 0 ≤ y ≤ M)

출력

욱제가 트램펄린으로 최대한 많은 별똥별을 튕겨낼 때, 지구에 부딪히는 별똥별의 개수를 출력한다.

예제 입력

예제 출력

백준 14658번 문제

💡Idea

브루트포스로 접근을 하면 시간 초과가 발생하는 문제입니다.

👇 브루트포스로 푼 코드

import sys
input = sys.stdin.readline
N, M, L, K = map(int, input().split())
pos = [tuple(map(int, input().split())) for _ in range(K)]
ans = K

if N <= L and M <= L:
    print(0)
    exit()

for i in range(min([p[0] for p in pos]), max([p[0] for p in pos]) - L + 1):
    for j in range(min([p[1] for p in pos]), max([p[1] for p in pos]) - L + 1):
        stars = 0
        for p in pos:
            if i <= p[0] <= i+L and j <= p[1] <= j+L: stars += 1
        ans = min(ans, K - stars)
print(ans)

따라서 아래와 같은 생각을 해보았습니다.

👩‍💻 : 별똥별이 떨어지는 각 점을 각각 정사각형의 왼쪽 위 / 왼쪽 아래 / 오른쪽 위 / 오른쪽 아래 꼭짓점으로 하는 경우들을 고려해보면 어떨까?

import sys
input = sys.stdin.readline
N, M, L, K = map(int, input().split())
pos = [tuple(map(int, input().split())) for _ in range(K)]
ans = 0

for x, y in pos:
    temp = [0] * 4
    for nx, ny in pos:
       if x - L <= nx <= x and y - L <= ny <= y: temp[0] += 1 # 오른쪽 위 꼭짓점
       if x - L <= nx <= x and y <= ny <= y + L: temp[1] += 1 # 오른쪽 아래 꼭짓점
       if x <= nx <= x + L and y - L <= ny <= y: temp[2] += 1 # 왼쪽 위 꼭짓점
       if x <= nx <= x + L and y <= ny <= y + L: temp[3] += 1 # 왼쪽 아래 꼭짓점
    ans = max(ans, *temp)
print(K - ans)

그래서 별똥별이 떨어지는 각 점을 트램펄린의 4개의 꼭짓점으로 가정한 뒤, 가장 많은 별똥별을 튕겨낼 수 있는 배치를 찾아보았습니다.

하지만 이렇게 구하면 아래와 같은 경우에서의 최적의 배치를 찾아낼 수 없습니다.

따라서, 위와 같은 경우까지 구하기 위해서는 아래와 같은 방식으로 문제를 해결해야 합니다.

두 점을 선택하여, 두 점이 걸쳐지는 점을 왼쪽 아래 꼭짓점으로 하여 가장 많은 별들을 튕겨낼 수 있는 배치를 찾는다.

예를 들어, 위의 그림에서는 (2, 6)과 (6, 2)가 걸쳐지는 점인 (2, 2)가 왼쪽 아래 꼭짓점이 될 때 가장 많은 별들을 튕겨낼 수 있습니다.

💻코드

⏰ 시간 : 280 ms / 메모리 : 30840 KB

import sys
input = sys.stdin.readline
N, M, L, K = map(int, input().split())
pos = [tuple(map(int, input().split())) for _ in range(K)]
ans = 0 

for fx, fy in pos:
    for sx, sy in pos:
        stars = 0
        for px, py in pos: 
            if fx <= px <= fx + L and sy <= py <= sy + L: stars += 1
        ans = max(ans, stars)
print(K - ans)