코딩 테스트 일기 - 15일 차

두 원 사이의 정수 쌍

문제 링크 : 두 원 사이의 정수 쌍

문제 설명

x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.
※ 각 원 위의 점도 포함하여 셉니다.

제한 사항

• 1 ≤ r1 < r2 ≤ 1,000,000

입출력 예

r1	r2	result
2	3	20

풀이 방법

• 제 1사분면을 기준으로 해서 피타고라스 정리를 통해서 안의 원, 바깥의 원 내부에 찍을 수 있는 점을 구해서 곱하기 4를 할 예정이다. 바깥의 원은 점의 개수를 floor()를 통해 구하고, 안쪽의 원은 점의 개수를 ceil()을 통해 구하는 것이 문제의 핵심인 것으로 보인다. 왜냐하면 안쪽의 원은 만약에 점과 겹칠 경우에 포함되어야 하기 때문이다.
  -> 시간복잡도는 O(N)으로 N은 가장 큰 r2 값으로 최대 1,000,000이기 때문에 알맞은 알고리즘으로 보인다.

구현

#include <string>
#include <vector>
#include <cmath>

using namespace std;

long long solution(int r1, int r2) {
    long long answer = 0;
    
    for(long long i = 1; i <= r1; i++){
        long long big = floor(sqrt(pow(r2, 2) - pow(i, 2)));
        long long small = ceil(sqrt(pow(r1, 2) - pow(i, 2)));
        answer += big - small + 1;
    }
    
    for(long long i = r1 + 1; i <= r2; i++){
        long long big = floor(sqrt(pow(r2, 2) - pow(i, 2)));
        answer += big + 1;
    }
    
    return answer * 4;
}