난이도: Level 2
언어: Python
핵심 개념: 수학, 피타고라스 정리, 정수 제곱근
1. 문제 소개
수학 문제이다. 이 문제는 쉬운 편이지만.. 개인적으로는 어렵게 가자면 수학문제가 많이 까다로웠다.
양의 정수 k와 d가 주어졌을 때, 다음 조건을 만족하는 좌표평면 위의 점의 개수를 구하는 문제다.
- x좌표와 y좌표는 모두 0 이상의 k의 배수여야 한다.
- 원점 (0, 0)으로부터의 거리가 d 이하여야 한다.
- 원의 경계에 위치한 점도 포함한다.
제한사항
- 1 ≤ k ≤ 1,000,000
- 1 ≤ d ≤ 1,000,000
입출력 예시
| k | d | result |
| 2 | 4 | 6 |
| 1 | 5 | 26 |
2. 핵심 아이디어
이 문제의 핵심은 모든 좌표를 하나씩 확인하지 않고, x좌표를 고정한 뒤 가능한 y좌표의 개수를 한 번에 계산하는 것이다.
모든 (x, y) 조합을 확인하면 이중 반복문이 필요하지만, 원의 방정식을 이용하면 하나의 반복문으로 해결할 수 있다.
① x좌표 고정하기
x좌표는 0, k, 2k, 3k, ... 순서로 이동한다.
하나의 x좌표가 정해지면 원점과의 거리 조건에 따라 가능한 y좌표의 최댓값을 계산할 수 있다.
원의 내부에 존재하는 점은 다음 조건을 만족한다.
x² + y² ≤ d²
따라서 y좌표의 최댓값은 √(d² - x²)이다.
② 가능한 y좌표 개수 구하기
예를 들어 k = 2, d = 4이고 x = 2라면 다음과 같다.
- y의 최댓값은 √12 ≈ 3.46이다.
- y는 2의 배수여야 한다.
- 따라서 가능한 y좌표는 0, 2로 총 2개다.
이 계산을 Python으로 표현하면 다음과 같다.
max_y = isqrt(d * d - x * x)
count = max_y // k + 1isqrt()로 y좌표의 정수 상한을 구하고, // k + 1로 가능한 좌표의 개수를 계산한다.
마지막에 1을 더하는 이유는 y = 0인 경우도 포함하기 때문이다.
③ 모든 x좌표에서 개수 더하기
각 x좌표에 대해 가능한 y좌표의 개수를 구한 뒤 모두 더하면 정답이 된다.
k = 2, d = 4인 경우 다음과 같다.
| x좌표 | 가능한 y좌표 | 점의 개수 |
| 0 | 0, 2, 4 | 3 |
| 2 | 0, 2 | 2 |
| 4 | 0 | 1 |
| 합계 | - | 6 |
3. 풀이 과정 시각화
아래 이미지에서는 원의 내부에 존재하는 점과 각 x좌표에서 가능한 y좌표의 개수를 확인할 수 있다.
특히 x좌표가 증가할수록 가능한 y좌표의 범위가 줄어드는 모습에 주목하면 풀이 원리를 쉽게 이해할 수 있다.
4. Python 정답 코드
from math import isqrt
def solution(k, d):
answer = 0
for x in range(0, d + 1, k):
max_y = isqrt(d * d - x * x)
answer += max_y // k + 1
return answer5. 코드 해설
① 가능한 x좌표 순회
for x in range(0, d + 1, k):0부터 d까지 k 간격으로 x좌표를 순회한다.
② y좌표의 최댓값 계산
max_y = isqrt(d * d - x * x)피타고라스 정리를 이용해 현재 x좌표에서 허용되는 y좌표의 최댓값을 구한다.
isqrt()는 정수 제곱근을 반환하므로 소수점 오차 없이 계산할 수 있다.
③ 점의 개수 누적
answer += max_y // k + 1현재 x좌표에서 가능한 y좌표의 개수를 구해 정답에 더한다.
이 과정을 모든 x좌표에 반복하면 전체 점의 개수를 구할 수 있다.
6. 시간 및 공간 복잡도
시간 복잡도: O(d/k + 1)
x좌표를 k 간격으로 순회하므로 반복 횟수는 d // k + 1이다.
일반적인 코딩 테스트의 연산 비용 모델에서는 각 반복의 계산을 상수 시간으로 취급한다.
모든 좌표 조합을 확인하는 O((d/k + 1)²) 방식보다 효율적이다.
공간 복잡도: O(1)
추가적인 배열이나 자료구조를 사용하지 않고 변수 몇 개만 사용한다.
7. 핵심 정리
이 문제에서 기억해야 할 것은 다음과 같다.
- 이중 반복문을 수학적 계산으로 대체하면 탐색 횟수를 크게 줄일 수 있다.
- x좌표를 고정하면 피타고라스 정리로 가능한 y좌표의 범위를 구할 수 있다.
- isqrt()와 정수 나눗셈을 활용하면 가능한 점의 개수를 정확하게 계산할 수 있다.
핵심은 점을 하나씩 세는 것이 아니라, 특정 x좌표에서 찍을 수 있는 점의 개수를 한 번에 계산하는 것이다.