[프로그래머스/Python] 두 원 사이의 정수 쌍

문제 정보

제목 : 두 원 사이의 정수 쌍

난이도 : Lv.2

사용 언어 : Python

문제 링크

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

프로그래머스

 

문제 설명

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

 

제한 사항

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

입출력 예

r1	r2	result
2	3	20

 

입출력 예 설명

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

---

나의 풀이

작은 원(r1)과 큰 원(r2) 사이의 정수를 구하는 문제입니다. x축과 y축을 기준으로 동일한 패턴이 반복되므로 제 1 사분면을 기준으로 값을 구해서 *4를 합니다.

x가 1부터 r2+1만큼 반복하는 for루프를 이용하는데 1부터 시작하는 이유는 중복되는 부분 없이 패턴이 반복될 수 있도록 하기 위함입니다. y의 최소와 최대값을 구해 그 사이의 정수를 구하는데, 작은 원의 경우는 현재 위치보다 큰 값이 개수에 포함되니 올림을, 큰 원의 경우는 현재 위치보다 작은 값이 개수에 포함되니 내림을 처리하면됩니다.

그리고 y의 값을 구하기 위해 원의 방정식을 이용합니다.

원의 방정식 : r² = x² + y²  →  y² = r² - x²      ∴ y = √( r² -  x² )

 

이 원의 방정식을 순서대로 대입해보겠습니다.

ex) r1 = 2, r2 = 3

    for x in range(1,r2+1) :
        maxY = math.floor( math.sqrt(r2**2 - x**2) )
        minY = 0 if x >= r1 else math.ceil( math.sqrt( abs(r1**2 - x**2) ) )

① x = 1

maxY = floor( sqrt(3² - 1²) ) 이므로 대략  2.82가 나오고 내림하면 2가 나옵니다.

x가 r1보다 작으니 else문이 실행되어 ceil( sqrt( abs(2² - 1²) ) )이므로 대략 1.73 정도 나오고 올림하면 2가 됩니다.

answer에는 maxY - minY + 1를 저장하므로 2 - 2 + 1이 되어 1개가 됩니다.

 

② x = 2

maxY = floor( sqrt(3² - 2²) ) 이므로 대략  2.23가 나오고 내림하면 2가 나옵니다.

x가 r1이랑 같아서 0이 됩니다.

answer에는 maxY - minY + 1를 저장하므로 2 - 0 + 1이 되어 3개가 됩니다.

 

③ x = 3

maxY = floor( sqrt(3² - 3²) ) 이므로 0이 나옵니다.

x가 r1이랑 같아서 0이 됩니다.

answer에는 maxY - minY + 1를 저장하므로 0 - 0 + 1이 되어 1개가 됩니다.

 

이 값들은 제 1사분면에서의 값이므로 answer에 *4를 하면 원의 정수 쌍 개수가 나오게 됩니다.

 

코드

import math

def solution(r1, r2):
    answer = 0
    
    for x in range(1,r2+1) :
        maxY = math.floor( math.sqrt(r2**2 - x**2) )
        minY = 0 if x >= r1 else math.ceil( math.sqrt( abs(r1**2 - x**2) ) )
        answer += maxY - minY + 1
        
    return answer * 4