Lv 2. 두 원사이의 정수 쌍

 

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

프로그래머스

 

 

 

두 개의 원 사이에 존재하는 격자점의 개수를 계산하는 문제다.

 위의 이미지를 보면 두 개의 원이 그려져 있다. 

작은 원은 반지름 r1​ , 큰 원은 반지름 r2 를 가지고 있다. 

이 두 원 사이에 포함된 정수 좌표를 찾는 것이 문제의 핵심이다. 

그림을 보면 두 원 사이에 위치한 파란색 점들이 우리가 찾으려는 정수 좌표들이다. 

코드는 각 x 좌표에서 y 값의 범위를 계산해 파란색 점들의 개수를 세는 방식으로 동작한다.

원의 방정식인 x제곱 + y제곱 = r제곱 를 사용하여

특정 x 좌표에서 가능한 y 값의 범위를 구할 수 있다.

예를 들어, x 값이 고정되었을 때,

작은 원 r1 의 방정식에 의해 계산된 y 값은 y의 하한선이 되고,

큰 원 r2 의 방정식에 의해 계산된 y 값은 y의 상한선이 된다.

 

이때 y 값은 반드시 정수여야 하므로,

하한선에는 올림을, 상한선에는 내림을 적용한다.

이 과정을 반복문을 통해 x 좌표가 1부터 r2​ 까지 순회하면서 수행한다.

각 x 좌표마다 계산된 y 값의 범위에서 가능한 정수 좌표의 개수는 end-start+1 로 구할 수 있다.

이 값을 누적하여 제1사분면에서 파란색 점들의 개수를 구한다.

최종적으로 이 값에 4를 곱해 전체 원(4개의 사분면)에 걸친 모든 격자점을 계산한다.

코드에서 Math.sqrt는 원의 방정식을 기반으로 y 값을 계산하기 위해 사용된다. 

Math.ceil과 Math.floor는 정수 범위를 한정하기 위한 중요한 역할을 한다. 

 

 

 

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;

        for (int i = 1; i <= r2; i++) {
            int start = (int) Math.ceil(Math.sqrt((long) r1 * r1 - (long) i * i));
            int end = (int) Math.floor(Math.sqrt((long) r2 * r2 - (long) i * i));

            answer += end - start + 1;
        }

        return answer * 4;
    }
}