문제 링크

문제 소개

해당 문제는 제공되는 좌표에 LxL를 최대로 담아냈을 때 그 밖의 별똥별 좌표의 개수를 물어보는 문제이다.

문제를 봤을 때, 1 ≤ N, M ≤ 500,000이기 때문에 전체 탐색시 N과 M을 기준으로 돌리면 100% 시간초과가 발생할 것이다.

그럼으로 우리는 K를 사용할 것이다.

해결책 1

우선 첫번째로 생각한 해결책은 별똥별 2개를 통해 사각형 영역을 구한 다음, 해당 영역의 좌측 상단을 기준으로 다른 별똥별들을 가져와보고 해당 영역에 존재하는지 확인하고 맞다면 카운트한다.

체크 조건은 아래와 같다.

두 별똥별의 사각형 영역의 좌측 상단의 좌표가 (x1,y1),(x2,y2)이고 우리가 보려는 별똥별의 좌표를 a,b일 때,
1-1. max(x1,x2) - min(x1,x2)가 최대 L이어야, 두 별똥별으로 사각형 영역을 구할 수 있음
1-2. max(y1,y2) - min(y1,y2)가 최대 L이어야, 두 별똥별으로 사각형 영역을 구할 수 있음
2-1. min(x1,x2) <= a <= max(x1,x2)일 경우 사각형 영역안에 우리가 보려는 별똥별이 들어갈 수 있음
2-2. min(y1,y2) <= a <= max(y1,y2)일 경우 사각형 영역안에 우리가 보려는 별똥별이 들어갈 수 있음

정리하자면, 2차 반복문을 통해 두 별똥별을 고르고, 두 별똥별이 들어가는 트램펄린 영역을 정한다음 다른 별똥별들을 하나씩 가져와서 해당 트램펄린 영역에 들어갈 수 있는지 카운트한다.

이러한 방식으로 코드가 성공되긴하나, 시간이 1188ms로 매우 많이 걸렸음으로 개선책이 필요해 보인다.

아래는 해결책 1의 최종 코드이다.

import sys


def solution():
    global N, M, L, K, cnt
    input = sys.stdin.readline
    N, M, L, K = map(int, input().split())
    stars = [list(map(int, input().split())) for _ in range(K)]
    ans = 1
    for i in range(K):
        for j in range(K):
            if i != j:
                cnt = 0
                checkWidth = lambda x,y:(max(stars[x][0], stars[y][0]) - min(stars[x][0], stars[y][0]) <= L)
                checkHeight = lambda x,y:(max(stars[x][1], stars[y][1]) - min(stars[x][1], stars[y][1]) <= L)
                width = lambda x, y, z: (min(stars[x][0], stars[y][0]) <= z <= min(stars[x][0], stars[y][0]) + L)
                height = lambda x, y, z: (min(stars[x][1], stars[y][1]) <= z <= min(stars[x][1], stars[y][1]) + L)
                for idx,val, in enumerate(stars):
                    x,y = val
                    if width(i, j, x) and height(i, j, y) and checkWidth(i,j) and checkHeight(i,j):
                        cnt += 1
                ans = max(ans, cnt)
    print(K - ans)


solution()

해결책 2

별똥별들의 좌표를 받을 때, 순서대로 받는게 아니기 때문에 sort함수를 사용해서 먼저 들어온 좌표가 좌측 상단으로 올 수 있도록 만든다.

이렇게 만드는 이유는 쓸데없는 연산을 줄이기 위함이다. 이렇게 정렬했다면 우선 아래와 같은 조건으로 답을 찾을 것이다.

1. 어떠한 별똥별(A)과 다른 별똥별들을 하나씩 비교해가며 x좌표만 봤을 때, 같은 트램펄린을 탈 수있는 좌표들의 y좌표만 저장해둔다.
2. 1번에서 저장한 y좌표에서 특정한 것을 하나 고른다음 다른 좌표들과 비교해서 같은 트램펄린을 탈 수 있는지 확인하고 개수를 카운팅한다.

이 해결책 2번의 핵심은 우선 x좌표를 먼저 생각한 다음, y좌표를 생각하는 것이다.

그리고 해결책 1번과 2번에서 보듯이 특정 별똥별의 좌표를 좌측 상단으로 박아두고 다른 별똥별들과 같은 트램펄린으로 묶을 수 있는지 보는게 이번 문제의 가장 핵심이라 할 수 있겠다.

다음은 해결책 2번의 최종 코드이다.

import sys


def check(stars):
    ans = 0
    for i in range(K):
        arr = []
        for j in range(i, K):
            if stars[j][0] <= stars[i][0] + L:
                arr.append(stars[j][1])
        arr.sort()
        for a in range(len(arr)):
            cnt = 0
            for b in range(a, len(arr)):
                if arr[b] <= arr[a] + L:
                    cnt += 1
            ans = max(ans, cnt)
    print(K - ans)


def solution2():
    global L, K
    input = sys.stdin.readline
    N, M, L, K = map(int, input().split())
    stars = sorted([list(map(int, input().split())) for _ in range(K)])
    check(stars)


solution2()