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

문제링크

---

두 원 사이의 정수 쌍

풀이과정

---

처음에 원은 $x^2 + y^2 = r^2$ 공식을 이용하면 되겠지 ? 라고 생각해서 1사분면에서 나올 수 있는거만 구하고 4를 곱했다. 근데 이렇게해서 풀리면 레벨 2겠냐구요 ㅋㅋ

당연히 나와 함께한 시간초과 ... 인정합니다 ...

Nyugati님 Tistory에서 그림을 보고 바로 이해했다. 친절한 그림과 함께 ... 최고야 짜릿해

아래는 블로그에 써있던 풀이이다.

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를 곱하여 전체 사분면의 정수 쌍의 개수를 구한다.

코드

---

import math

def solution(r1, r2):
    quarter = 0

    pr1, pr2 = r1 ** 2, r2 ** 2
    for i in range(1, r2+1):
        s = math.ceil(math.sqrt(pr1 - i ** 2)) if i < r1 else 0
        
        e = int(math.sqrt(pr2 - i ** 2))
        quarter += e - s + 1

    return 4 * quarter

결과

---