문제 개요
반지름 r 이내의 주변 환경을 감시할 수 있는 센서 모듈이 있다고 가정해 봅시다. 이 센서의 감시 원(원주) 위에는 반드시 감시해야 하는 격자점(lattice point)들이 몇몇 존재합니다. 이때 저전력 모듈 k개를 배치하여 해당 지점들만 감시하도록 구성하려고 합니다. 반지름의 제곱과 저전력 모듈의 개수 k가 주어졌을 때, 모든 지점을 올바르게 감시할 수 있는지 판별하는 프로그램을 작성해야 합니다. 감시가 가능하면 True를, 그렇지 않으면 False를 반환합니다.
입출력 예시
예를 들어 반지름의 제곱 j = 4, 감시 지점의 개수 k = 3이 입력되면 출력은 False가 됩니다. j = 4일 때 감시 원의 원주 위에는 (0, 2), (0, -2), (2, 0), (-2, 0)의 총 4개 격자점이 존재합니다. 따라서 감시 스테이션을 3개만 새로 설치하면 모든 지점을 완벽하게 커버할 수 없습니다.
해결 전략
이 문제는 다음 단계를 통해 해결할 수 있습니다.
- 완전제곱수 집합 생성: 44721 이하 정수들의 제곱값을 미리 집합(square_set)에 저장합니다. 덕분에 완전제곱수 여부를 O(1) 시간에 확인할 수 있어 탐색 속도가 크게 향상됩니다.
- 카운터 초기화: i := 0, res := 0으로 초기화합니다.
- 탐색 반복: i가 √j보다 작은 동안, (j − i²) 값이 square_set에 존재하면 res를 1 증가시키고 i를 1 증가시킵니다.
- 대칭성 활용: 최종적으로 res에 4를 곱해 원주 위 전체 격자점의 개수를 계산합니다.
- 판별: k ≥ res이면 True를, 그렇지 않으면 False를 반환합니다.
핵심 아이디어는 원의 방정식 x² + y² = j에 있습니다. x좌표 후보 i를 하나씩 검사하면서 j − i²이 완전제곱수가 되는 경우를 찾으면, 그 순간 (i, y) 형태의 유효한 격자점 조합을 발견한 것입니다. 원은 네 방향 부호에 대해 대칭이므로, 찾은 개수에 4를 곱하면 원주 위 전체 격자점의 개수가 됩니다. 마지막으로 이 총 개수를 k와 비교하여 충분한지 여부를 판단합니다.
구현 코드
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
square_set = set([z ** 2 for z in range(44722)])
def solve(j, k):
i = 0
res = 0
while i < (j ** 0.5):
if j - i ** 2 in square_set:
res += 1
i += 1
res *= 4
if k >= res:
return True
else:
return False
print(solve(4, 3))
실행 결과
입력:
4, 3
출력:
False
마무리
이 알고리즘은 완전제곱수 집합을 미리 구축해 두는 전처리 기법과 원의 대칭성을 결합하여, 원주 위 격자점의 개수를 효율적으로 계산합니다. 이를 통해 주어진 k개의 저전력 모니터링 스테이션으로 모든 감시 지점을 커버할 수 있는지 빠르고 정확하게 판별할 수 있습니다.