프로그래머스 | 두 원 사이의 정수 쌍 | python 풀이

문제

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

프로그래머스

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

내 답안

import math

def solution(r1, r2):
    answer = 0
    for i in range(1, r2+1):
        if i < r1 :
            s = math.ceil(math.sqrt((r1**2 - i**2)))
        else : 
            s = 0

        e = int(math.sqrt((r2**2 - i**2)))
        answer = answer + e - s + 1

    return answer*4

해설

처음엔 r1^2 <= x^2 + y^2 <= r2^2 를 만족하는 모든 쌍을 구했다가 시간초과가 났다.

 

그래서 1사분면 기준으로 모든 정수 쌍의 개수를 구한 뒤 곱하기 4를 해주는 방식으로 풀었다.

 

참고 그림(출처 : 나)

풀이는 다음과 같다.

1. i를 1 ~ r2 까지 순회하면서 x = i 와 두 원의 방정식과의 교점(s,e)을 구한다.

• s는 정수 쌍 속하는 범위의 시작이 되고, e는 범위의 끝이 된다.
  • 반지름이 r2인 원과 x=i인 직선의 교점에서 내림(int 혹은 math.floor)을 적용하여 범위의 끝 값인 e를 구한다.
  • i 값이 r1보다 작으면, 반지름이 r1인 원과 x=i인 직선에서 x좌표가 0이 아닌 교점이 존재하므로 올림을 적용하여(math.ceil) 범위의 시작인 s값을 구한다.
  • i값이 r1보다 크거나 같다면 범위의 시작 s는 무조건 0이다.

2. s와 e 사이에 속하는 모든 정수의 개수를 구하고 answer 값에 더한다.
3. for문 순회 후 도출된 answer 값에 4를 곱하여 전체 사분면의 정수 쌍의 개수를 구한다.

피드백

수학을 잘하는 모든 사람이 알고리즘을 잘 푸는 건 아니지만, 알고리즘을 잘 푸는 사람들 중에 수학 못하는 사람은 없다는걸 다시 한 번 느꼈다.