[2] 두 원 사이의 정수 쌍 - 181187

문제 링크

문제 링크

성능 요약

메모리: 4.15 MB, 시간: 3.57 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 100.0
합계: 100.0 / 100.0

문제 설명

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

---

제한 사항

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

---

입출력 예

r1	r2	result
2	3	20

---

입출력 예 설명

그림과 같이 정수 쌍으로 이루어진 점은 총 20개 입니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

코드

#include <bits/stdc++.h>

using namespace std;

long long solution(int r1, int r2) {
    long long answer = 0; // 결과값을 저장할 변수 초기화

    answer -= r2 - r1 + 1; // 두 원의 반지름 차이만큼의 값 조정 (음의 값 시작)

    long long R1 = (long long)r1 * r1; // 반지름 r1에 대한 제곱값 (R1 = r1^2)
    long long R2 = (long long)r2 * r2; // 반지름 r2에 대한 제곱값 (R2 = r2^2)

    // x 좌표가 0부터 r2까지 변하는 경우를 순회
    for (int x = 0; x <= r2; x++) {
        long long xx = (long long)x * x; // 현재 x의 제곱값 (xx = x^2)

        // r2에 해당하는 원의 y 값의 최댓값을 구함
        int t2 = sqrt(R2 - xx); // sqrt(R2 - x^2): y^2 <= R2 - x^2인 y의 최대값 t2
        
        int t1;
        // x가 r1보다 작은 경우, r1에 해당하는 y 값의 최소값을 구함
        if (x < r1) {
            double td = sqrt(R1 - xx); // sqrt(R1 - x^2): y^2 >= R1 - x^2인 y의 실수값 td
            int ti = sqrt(R1 - xx);    // 해당 y의 정수 부분 ti
            t1 = td > (double)ti ? ti + 1 : ti; // 만약 td가 정수 ti보다 크다면, ti + 1로 반올림
        } else {
            t1 = 0; // x >= r1일 때, 최소값은 0
        }
        
        // t2 - t1 + 1은 현재 x 값에 대해 y 좌표의 가능한 개수
        answer += t2 - t1 + 1;
    }
    
    return answer * 4; // 1사분면 값만 계산했으므로, 전체 영역(4사분면)에 대해 4를 곱함
}