풀이 과정
- x가 1부터 r2일 때까지 반복
- 해당 시점에서 y의 최댓값, 최솟값 구하기
- 대각선 길이 구하는 x^2 + y^2 = r^2을 이용해서 y^2 = r^2 - x^2
- 이때 큰 원의 경계는 포함하지 않도록 버림, 작은 원의 경계는 포함하도록 올림
- i가 r1보다 크거나 같다면 0으로 처리해서 x축 위의 점까지 세기
- 1사분면의 점 개수만 센 것이므로 결과는 4를 곱하기
코드
function solution(r1, r2) {
let result = 0;
for (let i = 1; i <= r2; ++i) {
let maxY = Math.floor(Math.sqrt(r2 ** 2 - i ** 2));
let minY = i >= r1 ? 0 : Math.ceil(Math.sqrt(r1 ** 2 - i ** 2));
result += maxY - minY + 1;
}
return result * 4;
}🤔
1시간 넘게 고민했는데도 답이 안 나와서 다른 사람들의 풀이를 참고했다.
O(n^2)을 O(n)으로 줄이는 건 항상 어려운 것 같다.
