[Algorithm] Programmers :: 두 원 사이의 정수 쌍

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

프로그래머스

 

 

long long solution(int r1, int r2) 
{
    long long answer = 0;
 
    for (int x = 1; x <= r2; ++x)
    {
        int minY = ceil(sqrt((long long)r1 * r1 - (long long)x * x));
        int maxY = floor(sqrt((long long)r2 * r2 - (long long)x * x));
 
        if (x >= r1) minY = 0;
 
        answer += (maxY - minY + 1);
    }
 
    return answer * 4;
}

 

x^2 + y^2 = r^2 라는 원의 방정식을 이용한 풀이이다.

식을 수정하면 y^2 = r^2 - x^2이며, y = 루트r^2 - x^2이다.

즉, x축에서의 각 최소,최대의 y값을 구해서 그 차를 이용해 두 원 사이의 정수 쌍을 구하는 문제이다.

작은원과 큰 원 사이이기 때문에, minY(작은원에서의 y좌표값)은 반올림해주고 maxY(큰 원에서의 y좌표값)은 반내림 해준다. 

 

그리고 반복문을 1부터 r2까지 (x축 1부터 r2까지) 해준다는것도 중요하다. 0부터하면 겹치는값이 생기기때문에 오버된 값이 나온다. 1부터해야 해당분면에서의 적절한 점의 개수가 나오기 때문에, 하나의 분면에서 구한값 * 4가 정답이 될 수 있다.

잘 이해가 안되면 1사분면에서 1부터 r2까지 점을 찍은다음 그대로 왼쪽으로 90도 회전시켜보면 된다.