https://school.programmers.co.kr/learn/courses/30/lessons/181187

📒문제

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.
※ 각 원 위의 점도 포함하여 셉니다.

r1	r2	result
2	3	20

✔️제한사항

1 ≤ r1 < r2 ≤ 1,000,000

📒풀이

import math

def solution(r1, r2):
    answer = 0
    
    for i in range(1, r2+1):
    	# x가 r1을 넘어가는 경우 해당 공식을 만족할 수 있는 좌표가 없기 때문에 0으로 설정한다.
        minH = 0 if i > r1 else math.ceil(math.sqrt((pow(r1, 2) - pow(i, 2))))
        maxH = math.floor(math.sqrt((pow(r2, 2) - pow(i, 2))))
        answer += (maxH - minH + 1) 

    answer *= 4
    return answer

원의 방정식을 이용 한 풀이

원의 방정식이란

원점으로부터 원 위의 임의의 점 모두에 적용되는 공식으로

원점 O(x1, y1)에서 원 위의 임의의 점 P(x2, y2)가 있다면

(x2 - x1) ^ 2 + (y2 - y1) ^ 2 = r2이다.

해당 문제는 원점이 모두 (0, 0)이므로 x^2 + y^2 = r^2 이라고 할 수 있다.

이 공식을 이용해서 y^2 = r^2 - x^2이므로 반복문을 통해 x를 하나씩 늘려가며 y를 구해 가능한 좌표를 하나씩 구한다.

📒시간복잡도

O(r2)