[Programmers] Lv2. 두 원 사이의 정수 쌍 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

원은 상하좌우 대칭이므로, 4개의 사분면 중 하나에 속한 점들 개수만 구해서 4배 후, 겹치는 점 개수들만 빼주면 되겠다고 생각하였습니다. 저는 2사분면을 선택하여 진행하였습니다.

 

제 2사분면 내 점 개수(3개) * 4 + 겹치는 점 개수(8개) = 20개입니다.

 

아래 과정은 제 2사분면 내에 점들 개수를 구한다는 가정 하에 진행한 과정들입니다.

 

• 우리는 정수 부분만 택해야 하므로, 큰 원의 y값은 내림, 작은 원의 y값은 올림 처리를 해야 합니다.
• [a, b] 구간의 자연수 개수를 구하는 공식은 b - a + 1입니다. (a ≤ b)
• 큰 원을 r1, 작은 원을 r2라고 하면, r1.x \( \leq \) r2.x인 경우에는 항상 y = 0에 점이 생깁니다.
  • r1.x - r2.x + 1이 곧, -x 방향에서의 y = 0 점 개수가 됩니다.
  • 이것은 -x 방향, x 방향, -y 방향, y 방향 모두 같게 적용되므로 겹치는 점의 총 개수는 (r1.x - r2.x + 1) * 4입니다.
  • 해당 개수를 나중에 더해주면 됩니다.
• r1.x > r2.x인 경우에는 x < 0일 때까지 겹치는 점이 발생하지 않습니다.
• x < 0일 때까지 제 2사분면 내의 점 개수를 다 구했다면, 해당 점 개수를 4배한 후, 겹치는 점의 개수를 더해주면 답이 됩니다.

 

✏️소스 코드 및 결과

#include <cmath>
#include <algorithm>
using namespace std;

long long GetYValue(long long x, long long r, bool onCeil) {
    double y = sqrt(r * r - x * x);
    return onCeil ? ceil(y) : floor(y);
}

long long solution(int r1, int r2) {
    if (r1 < r2)      // r1이 더 큰 원이라고 가정
        swap(r1, r2);
    long long answer = 0;
    long long overlapPoints = (r1 - r2 + 1) * 4;

    // 2사분면 내(x, y축 제외) 점 개수 구하기
    for (int x = -r1 + 1; x < 0; x++) {
        long long r1Y = GetYValue(x, r1, false);

        // x <= -r2인 경우에는 y = 0 점을 제외시키도록 1로 설정
        long long r2Y = (x > -r2) ? GetYValue(x, r2, true) : 1;
        long long upperPointCount = r1Y - r2Y + 1;
        answer += upperPointCount;
    }

    return answer * 4 + overlapPoints;
}