[Programmers/Python] 두 원 사이의 정수 쌍

Programmers - 두 원 사이의 정수 쌍

---

문제

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

제한 사항

• 1 ≤ r1 < r2 ≤ 1,000,000

입출력 예

r1	r2	result
2	3	20

입출력 예 설명

그림과 같이 정수 쌍으로 이루어진 점은 총 20개 입니다.

---

풀이

설계

1. 각 사분면에 존재하는 정수 쌍의 개수가 동일하므로 우선 2사분면, 즉 양수값으로 이루어진 정수쌍만을 구하여 4를 곱한다.
2. x의 범위를 1부터 r2까지로 하여 각 x의 값에 따른 y값의 최소치와 최대치를 구한다.
3. 최대치(y_max)는 큰 원의 둘레(r2의 제곱)에서 x의 제곱을 뺀 뒤 루트를 씌운 값을 '내려서' 구한다.
   • r2가 3, x가 1인 경우 sqrt((3 2) - (1 2)) = 2.8284...이므로 이 값을 내림하면 2가 된다.
4. 최소치(y_min)는 작은 원의 둘레(r1의 제곱)에서 x의 제곱을 뺀 뒤 루트를 씌운 값을 '올려서' 구한다.
   • r1이 2, x가 1인 경우 sqrt((2 2) - (1 2)) = 1.7320...이므로 이 값을 올림하면 2가 된다.
5. y_max - y_min + 1을 하면 해당 x값에서 두 원 사이에 존재하는 정수 를 구한다.
   • r1과 r2가 각각 2와 3일 때, x가 1인 시점의 가능한 y의 값은 1(2)개가 된다.
   • r1과 r2가 각각 2와 3일 때, x가 2인 시점의 가능한 y의 값은 3(2, 1, 0)개가 된다.
6. answer에 4를 곱하면 최종 정답이 된다.

코드

import math

def solution(r1, r2):
    answer = 0

    # x가 1인 경우부터 개수 확인
    for x in range(1, r2+1):
        # 큰 원의 둘레 정수값 = y_max
        y_max = math.floor(math.sqrt(r2 ** 2 - x ** 2))

        # 작은 원의 둘레 정수값 = y_min
        if x >= r1:
            y_min = 0
        else:
            y_min = math.ceil(math.sqrt(r1 ** 2 - x ** 2))
        answer += y_max - y_min + 1

    return answer * 4