후기

내용

처음 떠올린 풀이

처음에는 x, y 좌표를 모두 순회하면서 각 좌표가 반지름 r1과 r2 사이에 있는지 직접 검사했습니다.

for (let x = 0; x <= r2; x++) {
    for (let y = 0; y <= r2; y++) {
        if (is_in(x, y, r2) && is_out(x, y, r1)) {
            // 점 개수 증가
        }
    }
}

각 좌표에 대해 다음 조건을 확인했습니다.

r1² ≤ x² + y² ≤ r2²

• x² + y² ≤ r2²: 바깥 원의 내부에 있는가?
• x² + y² ≥ r1²: 안쪽 원의 외부에 있는가?

그리고 축 위에 있는 점과 축 위에 있지 않은 점은 대칭되는 개수가 다르다고 생각하여 별도로 계산했습니다.

if (is_zero(x, y)) {
    have_zero += 1;
} else {
    not_have_zero += 1;
}

이 방식은 모든 점을 직접 확인하기 때문에 이해하기는 쉬웠지만, x와 y를 모두 반복하여 시간복잡도가 O(r2²)가 되었습니다.

즉, 시간 초과의 원인은 거리 계산 함수가 많아서가 아니라 다음 반복문 자체였습니다.

for (let x = 0; x <= r2; x++) {
    for (let y = 0; y <= r2; y++) {
    }
}

시간 초과를 해결하기 위해 바꾼 풀이

이중 반복문을 없애기 위해 x 하나를 고정하고, 그 x에서 가능한 모든 y를 직접 검사하지 않고 가능한 y의 시작과 끝만 계산하기로 했습니다.

원의 경계는 다음 식으로 표현할 수 있습니다.

x² + y² = r²

x를 이미 알고 있으므로 y를 구하면 다음과 같습니다.