문제
문제 설명
x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.※ 각 원 위의 점도 포함하여 셉니다.
제한 사항
- 1 ≤
r1<r2≤ 1,000,000
입출력 예
| r1 | r2 | result |
| 2 | 3 | 20 |
입출력 예 설명
그림과 같이 정수 쌍으로 이루어진 점은 총 20개 입니다.
풀이
주요 아이디어
원의 방정식
x²+y²=r² 공식을 사용해야만 한다.
시간 복잡도
-r ≤ x ≤ r, -r ≤ y ≤ r 범위 내에서 원의 방정식을 만족하는 x,y의 개수를 모두 구하게 되면
시간은 (2r) * (2r) → O(r^2)이 나온다.
하지만 주어진 범위가 • 1 ≤ r1 < r2 ≤ 1,000,000 이므로 O(r)이내로 들어와야 한다.
y 좌표 구하기
x는 -r ~ +r까지 계속 이동한다. → O(r)
원 위에 있는 점의 좌표가 (x, y)일 때, 원의 방정식을 통해 y 값을 구한다
x좌표일 때 원 내부에 있는 점의 개수 = -y ~ +y 사이에 있는 정수 좌표의 개수 = 2 * floor(y) + 1(원점)
원의 테두리에 있는 점의 개수 구하기 → bound(r)
큰 원의 점의 개수에서 작은 원의 점의 개수를 빼게 되면
결과값에서 작은 원의 테두리에 있는 점의 개수는 포함하지 않게 된다.
이를 위해 원의 테두리에 있는 점의 개수를 포함하는 함수를 구현한다.
코드
from math import sqrt, floor # 원 내부에 있는 좌표의 개수 (boundary 포함) def cir(r): cnt = 0 for x in range(-r, r+1): y = sqrt(r*r - x*x) # y의 좌표를 구함 y = floor(y) cnt += (2 * y + 1) # -y ~ +y 사이에 있는 정수 좌표의 개수 return cnt # boundary 위에 있는 점의 개수 세는 함수 def bound(r): cnt = 0 for x in range(-r+1, r): y = sqrt(r*r - x*x) if y == floor(y): cnt += 2 return cnt + 2 def solution(r1, r2): answer = cir(r2) - cir(r1) + bound(r1) return answer