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

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

프로그래머스

 

Status : Solved

 

Time : 00:20:01

 

---

 

문제 설명

 

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

 

입력 및 출력

 

제한사항

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

 

입출력 예

r1	r2	result
2	3	20

 

 

---

 

풀이

LV 2 문제도 조금은 생각해보아야 하는 문제가 나온 것 같다. 아니면 수학 특집이라 그런가...?

 

하나씩 점을 세다가는 무조건 시간 초과를 일으키므로(O(N^2) 소요) 조금 다르게 생각해 볼 필요가 있다. 우선, 4분면으로 회전변환이 가능하므로 1사분면(x > 0, y > 0)을 기준으로 구한 뒤 4배를 해 주면 된다. 또한 점을 '축 위에 있는 점'과 '그렇지 않은 점'으로 나누어 생각해보자.

 

• 축 위에 있는 점 : 간단하다. r1 <= x <= r2 사이에 있는 모든 정수 x의 개수를 구하면 되므로, r2 - r1 + 1이 될 것이다.
• 그렇지 않은 점 : 0보다 크고 r2보다 작거나 같은 각 y에 대해 생각해보자.
  • r2 원 상의 x좌표는 피타고라스 정리에 의해 sqrt(r2^2 - y^2)가 된다. 이를 maxval이라고 칭하자.
  • r1 원 상의 x좌표는 두 가지 경우로 갈린다. 만약 r1의 반지름보다 y가 작다면, 피타고라스 정리에 의해 sqrt(r1^2-y^2)가 될 것이다. 그렇지 않다면 점은 무조건 r1 원 밖에 벗어나 있으므로 0보다 조금 큰 어떤 값으로 둘 수 있을 것이다. 이를 minval이라고 칭하자.
  • 즉 이 경우에 총 점의 개수는 minval <= x <= maxval을 만족하는 모든 정수 x의 개수를 의미한다. 이를 모든 y에 대해 구해 더해주면 된다.

 

 

풀이 코드

from math import ceil, floor

def solution(r1, r2):
    answer = (r2 - r1 + 1) * 4
    for y in range(1, r2):
        maxval = floor((r2**2 - y**2) ** 0.5)
        if r1 <= y :
            minval = 1
        else :
            minval = ceil((r1**2 - y**2) ** 0.5)
        answer += 4*(maxval - minval + 1)
            
    return answer

풀이 완료~