[프로그래머스] 181187. 두 원 사이의 정수 쌍 | 수학 | 파이썬, 소스코드, 정답

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

프로그래머스

---

문제 요약

• 중심이 원점이고 반지름이 r1, r2인 두개의 원 존재
• 두 원 사이의 공간에서 x좌표와 y좌표가 정수인 점의 개수를 구하라

---

문제 조건

• 원 위의 점도 포함
• 1 <= r1 < r2 <= 1000000

---

시행착오

처음에는 r2 바깥 점의 개수와 r1 안에 있는 점의 개수를 2중 for문으로 일일이 세서 계산.

근데 당연히 시간초과뜸 ㅎㅎ;; 

그래서 다른분 풀이 봤는데 중첩반복문 안쓰고 수학적으로 풀 수 있다는 것을 알게됨

---

접근방법

1. 원이 원점에 존재하므로 한 사분면에 해당하는 점의 개수만 구하고 *4 하면 됨
2. 원의 방정식은 x*x + y*y = r*r임. x를 1~r까지 순회하면서 r2와 r1사이에 존재하는 y의 개수를 계산하면됨
3. y의 최대값은 floor(sqrt(r2*r2 - x*x)), y의 최소값은 만약 x가 r1보다 크면 0 아니면 ceil(sqrt(r1*r1 - x*x)). 

---

소스코드

from math import sqrt, ceil, floor

def solution(r1, r2):
    cnt = 0

    for x in range(1, r2+1):
        max_y = floor(sqrt(r2*r2 - x*x))
        min_y = 0 if x >= r1 else ceil(sqrt(r1*r1 - x*x))
        cnt += max_y - min_y + 1

    return cnt*4

---