[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 14658번 _ 하늘에서 별똥별이 빗발친다

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

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

[문제]

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

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

“에이, 거짓말!”

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

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

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

지구의 파괴를 막기 위해서는 지표면에 떨어지는 별똥별의 수를 최소화해야 한다. 욱제는 커다란 네모난 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)

[출력]

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

 

[아이디어]

1) n,m이 꽤 크기 때문에 후보가 되는 모든 격자에 대해 완전 탐색은 시간초과가 난다.(첫번째 풀이)

2) k의 값이 상대적으로 작음을 활용해, 후보가 되는 격자를 K*K개로 줄여놓고 완전 탐색을 실시한다. (개인적으로 이 부분은 그리디에 해당하지 않나 싶다.)

 

# 시간초과
n,m,l,k = map(int,input().split())
stars = []
for _ in range(k):
    a,b = map(int,input().split())
    stars.append((a,b))

length = l/2
x,y = length-1, length-1
ans = k
for i in range(n-l+1):
    x += 1
    y = length - 1
    for j in range(m-l+1):
        tmp = k
        y += 1
        for a,b in stars:
            if abs(x-a) <= length and abs(y-b) <= length:
                tmp -= 1
        ans = min(ans, tmp)
print(ans)

# 통과
n,m,l,k = map(int,input().split())
stars = []
for _ in range(k):
    a,b = map(int,input().split())
    stars.append((a,b))
ans = k
for x,_ in stars:
    for _,y in stars:
        tmp = k
        for a,b in stars:
            if x<= a <= x+l and y<= b <= y+l:
                tmp -= 1
        ans = min(ans, tmp)      
print(ans)

정답의 개수만큼만을 포함하지 못하는 격자는 여러 개일 수 있다. 이때 구하는 격자를 '특정 2개의 점을 경계에 포함하는 격자'로 한정한다면, 중복되는 격자에 대한 탐색을 하지 않고도 정답을 구할 수 있게 된다.

오른쪽 격자가 왼쪽 격자를 x축, y축 방향으로 각각 1씩 이동한 격자라고 생각해보자.

위 두 개의 격자는 모두 3개의 점을 내부에 포함하는데, k개의 점 중 임의의 2개의 조합을 통해 격자를 생성하여 탐색하는 방법으로 왼쪽의 케이스는 제외하고 오른쪽의 경우만 탐색하는 것을 목표로 한다. 모든 정답이 되는 격자는 오른쪽 격자와 같은 대표성을 띄는 케이스를 1개 이상 가지며, 왼쪽과 오른쪽의 경우는 격자의 위치만 다를 뿐 포함하는 점의 개수는 같으므로 답을 구하는데 문제가 없다.

따라서 첫 두 for문에서 x,y 좌표를 두 점으로부터 가져와 새롭게 (x,y)라는 좌하단 기준점을 형성하고, 이 기준점에 대해 각 K개의 점이 격자 내에 존재하는지 확인한다.