프로그래머스 두 원 사이의 정수 쌍 - C++ 풀이

---

 

1. -r2 ≤ k ≤ r2인 정수 k에 대해 x = k인 모든 점을 구한다.
2. 직선 x = k와 작은 원, 큰 원이 만나는 점의 양수 y 좌표를 각각 lo, hi라 하면 x = k인 점은 2 * (floor(hi) - ceil(lo) + 1)개이다.
3. | k | ≥ r1이면 2 * (floor(hi) + 1)개이다.

 

1. -r2 ≤ k ≤ r2인 정수 k에 대해 x = k인 모든 점을 구한다.

 x 좌표를 기준으로 -r2부터 r2까지 탐색하며 주어진 조건을 만족하는 점들의 개수를 구해나가자.

 

2. 직선 x = k와 작은 원, 큰 원이 만나는 점의 양수 y 좌표를 각각 lo, hi라 하면 x = k인 점은 2 * (floor(hi) - ceil(lo) + 1)개이다.

 두 원 사이의 공간에 위치한 점을 구해야 한다. x = k인 점의 개수를 구하기 위해서는 '직선 x = k와 두 원이 만나는 점의 양수인 y좌표'를 구한 뒤 그 사이에 위치하는 정수의 개수에 2배를 하면 된다.(음수인 y좌표도 있기 때문) 작은 원, 큰 원이 만나는 점의 좌표를 각각 lo, hi라 하면 [lo, hi]에 있는 정수의 개수는 floor(hi) - ceil(lo) + 1개이다. 따라서 총 2 * (floor(hi) - ceil(lo) + 1)개.

 두 원이 모두 만나는 k의 범위는 -r1 ≤ k ≤ r1 인데, y축을 기준으로 대칭이므로 0 ≤ k ≤ r1인 경우만 구해준 뒤 2배를 해주어도 된다. 이때 k = 0인 경우는 대칭인 상황이 없으므로 예외처리 해주었다. 또 k = r1인 경우에는 y = 0인 경우가 존재하므로 큰 원과만 만나는 경우와 동일하게 처리해주었다.

 

3. | k | ≥ r1이면 2 * (floor(hi) + 1)개이다.

 | k | > r1이면 큰 원과만 만난다. 큰 원과 직선 x = k가 만나는 점의 양수인 y좌표를 hi라고 하면, [-hi, hi]에 있는 정수의 개수는 2 * (floor(hi) + 1)개이다. 앞서 언급했듯 k = r1인 경우도 [-hi, hi]가 되므로 이 경우로 취급해주면 된다. 마찬가지로 y축 대칭이므로 r1 ≤ k ≤ r2인 경우만 구한 뒤 2배를 해주는 방법을 사용할 수 있다.

---

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

using namespace std;

typedef long long ll;
typedef long double ld;

ld intersection(ll x, ll r) {
    return sqrt(r*r - x*x);
}

long long solution(int r1, int r2) {
    long long answer = 0;
    
    // x = 0일 때
    answer += 2 * (r2 - r1 + 1);
    
    // x=1부터 x=(r1-1)까지
    for (ll x = 1; x < r1; x++) {
        ll hi = intersection(x, r2);
        ll lo = ceil(intersection(x, r1));
        answer += 4 * (hi - lo + 1);    // x<0, y<0 쪽도 있으므로 4배
    }
    
    // x=r1부터 x=r2까지
    for (ll x = r1; x <= r2; x++) {
        ll hi = intersection(x, r2);
        answer += 2 * (2*hi + 1);   // x<0 쪽도 있으므로 2배
    }
    
    return answer;
}