프로그래머스 Java Lv2 두 원 사이의 정수 쌍

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

 

 

해당 문제는 원의 방정식과 사분면을 이용하면 간단하게 풀 수 있다.

문제에서 요구하는 두 원 사이의 공간에서 x좌표와 y좌표가 모두 정수인 점들은 각 사분면에 대칭하는 것을 볼 수 있다.

 

그러므로 하나의 사분면에 존재하는 점들의 수를 구한뒤, 4를 곱하여 모든 점의 수를 계산할 수 있다.

 

그렇다면 하나의 사분면에 존재하는 점들의 수는 어떻게 구할까?

x좌표와 y좌표가 모두 정수인 점들이므로, x좌표가 정수인 경우 가능한 y좌표의 범위를 구하여 계산을 하였다.

 

이 때, 가능한 y좌표의 범위를 구하기 위해 원의 방정식을 이용하였다.

중심이 (a, b)인 원의 방정식 : (x-a)² + (y-b)² = r² 

 

 

문제의 예시로 생각해보자. ( 제 1사분면의 점들을 계산 )

x 좌표가 1인 경우, 큰 원의 y 값은 약 2.8, 작은 원의 y값은 1.7 이다.

이 때 가능한 범위는 2.8 이하인 정수, 1.7 이상인 정수이다. (이하, 이상인 이유는 원위의 점도 포함하므로)

 

범위에 포함되는 수를 바로 계산하기 위해 y값을 각각 내림, 올림 처리를 하고 그 차를 계산한다.

그리고 이하, 이상이므로 1을 더해주어야 한다.

2 이하인 정수, 2 이상인 정수 : ( 2 - 2 ) + 1 

 

이를 각 x 좌표에 따라 반복하고, 합을 계산한뒤 *를 곱하면 모든 점의 개수를 구할 수 있다.

 

 

*제 1사분면위의 점들을 계산할 때 주의할 점은 x좌표를 1 부터 시작해야한다.

 

만약 x좌표를 0 부터 시작하게 된다면 "y의 값이 0 이상인 축"과 "x의 값이 0 이상인 축"이 포함되는데,

이 상태에서 4를 곱하게 된다면 각 축들이 2번씩 포함되어 중복이 발생한다.

 

그러므로 x좌표를 1 부터 시작하여 "x의 값이 0 이상인 축" 만 포함되게 하여 4를 곱하여도 중복이 발생하지 않게 한다.

 

 

각각 x좌표를 0부터 시작한 경우, 1부터 시작한 경우이다.

0부터 시작한 경우 축이 겹치는 것을 볼 수 있다.

 

코드

class Solution {
    public long solution(int r1, int r2) {
        long answer = 0;
        
        // 4개의 사분면 중 1개만 구한뒤 4를 곱한다.
        for( int i = 1; i <= r2 ; i++){
            double y2 = Math.sqrt(Math.pow(r2,2) - Math.pow(i,2));
            double y1 = Math.sqrt(Math.pow(r1,2) - Math.pow(i,2));
            answer += ( (long)y2 - (long)Math.ceil(y1) + 1);
        }
        answer *= 4;
        
        return answer;
    }
}