python math 라이브러리 사용하여 두 수 사이의 정수값 구하기(올림, 내림, 제곱근)

                                    문제는 단순하다. 핵심 아이디어를 찾아보자

💡 사이에 존재하는 좌표이므로, 각 원을 지나는 정수 좌표도 해당된다.
💡 참고로 원은 대칭이므로 1사분면만 판단해도 상관없다.

💡 원의 방정식을 이용해보자
👉 x² + y² = r1² or r2²
>>> x, y >= 0 인 조건 (1사분면)
>>> x를 0부터 증가시켜서 만족하는 모든 좌표를 구할 수 있을 것 같다.

ex) x² + y² = 2² 과 x² + y² = 3²
>>> x = 0 -> y = 2, x = 0 -> y = 3
>>> (0, 2)와 (0, 3) 사이의 모든 정수 좌표 = 2개

>>> x = 1 -> y = root 3 , x = 1 -> y = root 8
>>> (1, root3) ~ (1, root8) 사이의 모든 정수 좌표 = (1, 2)

이렇게 해주고 y에 대해서도 0에서 부터 증가 시키기

                                    💡 아이디어 다듬기

1. 축에 속하는 좌표는 아래와 같이 구한다.
>>> 4 * (r2 - r1 + 1)
>>> 이는 항상 참 값이 된다.

2. 사이에 존재하는 좌표는 아래와 같이 구한다.
>>> x를 정수로 반복한다. 1 ~ r2 - 1 까지
>>> 1.5 ~ 7.6 사이의 정수 수는?
>>> 2 -> 7 사이의 정수 수와 같다. 7 - 2 + 1이다.

                                    def get_y(x, r): # x or y
    if x ** 2 > r ** 2:
        return 0
    return (r ** 2 - x ** 2) ** 0.5

def solution(r1, r2):
    answer = 0

    quad = 0
    axis = 0
    # 작은걸 기준으로
    for x in range(1, r2):
        # 0, 1, ..., r1

        # 축점 생각 x
        y1 = get_y(x, r1)
        y2 = get_y(x, r2)

        quad += int(int(y2) - int(y1 + 1) + 1)

    quad *= 4 #
    axis += (r2 - r1 + 1) * 4 # ok
    answer += quad + axis

    return answer

                                    😯 축이 아닌 점의 좌표중에서 작은원의 y값이 되는 부분을 간과했다..

>>> 추가 부분: math 라이브러리를 사용하자

🤬 실패의 원인
y1을 계산할 때 int(y1 + 1)로 해버려서
>>> 이렇게 되면 y가 축이 아님에도 정수인 케이스가 무시된다.
>>> 애초에 최소값을 1로 셋팅하면 된다.
>>> 정수인지 아닌지 구분해줘야 한다.

                                    import math

def solution(r1, r2):
    answer = 0

    quad = 0
    axis = 0
    r1_2 = r1 * r1
    r2_2 = r2 * r2
    # 작은걸 기준으로
    for x in range(1, r2):
        # 0, 1, ..., r1

        # 축점 생각 x
        y2 = math.floor(math.sqrt(r2_2 - x*x))

        if x*x >= r1_2:
            y1 = 1
        else:
            y1 = math.ceil(math.sqrt(r1_2 - x*x))

        quad += (y2 - y1) + 1

    quad *= 4 #
    axis += (r2 - r1 + 1) * 4 # ok
    answer += quad + axis

    return answer

✅ 시간복잡도
 O(r2)이다.

✅ 공간 복잡도
 모두 상수 변수라서 O(1)

                                    # in python

# math lib
import math
math.sqrt()  # 제곱근
math.floor() # 내림
math.ceil()  # 올림