[ 프로그래머스 ] 두 원 사이의 정수 쌍 (파이썬 python)

 

 

 

 

 

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

프로그래머스

 

 

 

 

 

💕풀이 방법

 

1️⃣ 원의 방정식을 사용해 y가 최솟값일 때, 최댓값일 때를 구해서 계산해 주면 되는 문제다.

단, 반지름의 최대 범위가 크기 때문에 모든 점들을 구하는게 아니라 1 사분면에 있는 점들을 구한 후 4를 곱해주면 된다
(예시 속 그림을 보면 대칭한다는 것을 알 수 있음)

 

원의 방정식 : x2+y2=r2

 

이제 원의 방정식을 사용해서 1사분면에 있는 두 원의 사이의 점들을 구해주면 된다.
2️⃣ 우선 x의 좌표는 1 부터 시작한다. 0부터 시작하게 되면 곱하기 4를 했을 때  x축과 y축의 점들이 중복으로 더해지기 때문이다. 따라서 x의 좌표는 1 ~ r2 까지가 된다.

 

3️⃣ 그리고 변경된 x값에 맞춰서 각각 y가 될 수 있는 최솟값과 최댓값을 구해준다. 이렇게 구한 최대값은 내림 처리, 최솟값은 올림 처리해 정수화 시키면 y값의 범위 사의의 정수 개수를 구 할 수 있다.

ex) r1 = 2, r2 = 3, x = 1 일때, y최댓값은 sqrt(r2 ** 2 - x ** 2)로 floor(2.xx) => 2 y의 최솟값은 sqrt(r1 **2 - x **2)로 ceil(1.xx) => 2가 된다. 이때 사이의 좌표의 개수는 y최댓값 - y최솟값 + 1을 해주면 x가 1 일 때 두 원 사이의 정수 쌍은 1개라를 것을 알 수 있다.

4️⃣ 단, x가 r1보다 크거나 같을 땐 y의 최솟값은 무조건 0이므로 최소값을 계산하지 않아도 된다.

 

 

 

 

 

💡 정답 코드

 

import math

def solution(r1, r2):
    answer = 0
    
    for x in range(1, r2 + 1):
        y_max = math.floor(math.sqrt(r2**2 - x**2))
        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