[Programmers] 181187번 - 두 원 사이의 정수 쌍 [Java][C++]

문제 링크

---

1. 문제 풀이

두 원 사이의 공간에 $x$, $y$ 좌표가 모두 정수인 점의 개수를 찾는 문제로 중심이 원점인 두 원이기 때문에 한 쪽 사분면에 대해서 판단한 후 $4$ 배를 해주면 전체 점의 개수를 구할 수 있다.

1사분면에 대해 정수인 점의 개수를 판단했는데 $x$ 좌표를 $1$ 부터 $1$ 씩 증가시키며 피타고라스 정리로 해당 $x$ 값에 대한 각 원에서의 $y$ 좌표를 찾았다. 두 $y$ 좌표 사이의 정수의 개수를 찾는 과정만 반복하면 1사분면에 대한 전체 점의 개수를 구할 수 있는데 큰 원의 $y$ 좌표에서 소수점 아래는 버림 처리하고, 작은 원의 $y$ 좌표는 소수점 아래에 대해 올림 처리를 해서 두 좌표 사이의 정수의 개수를 구할 수 있다.

해당 과정으로 1사분면에 포함되는 점의 수를 모두 구하면 $4$ 배를 해주면 되며, 1사분면의 점을 구할 때 양의 방향 $x$ 축 위의 점들도 구할 수 있어서 좌표축 위의 점들도 모두 잘 구할 수 있다.

---

2. 코드

1. 풀이 [Java]

class Solution {
    public long solution(int r1, int r2) {
        long ans = 0;

        for (long x = 1; x <= r2; x++) {
            int max = (int) Math.sqrt((long) r2 * r2 - x * x);
            int min = (int) Math.ceil(Math.sqrt((long) r1 * r1 - x * x));
            ans += max - min + 1;
        }

        return ans * 4;
    }
}

2. 풀이 [C++]

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

using namespace std;

long long solution(int r1, int r2) {
    long long ans = 0;

    for (long long x = 1; x <= r2; x++) {
        long long mx = sqrt((long long)r2 * r2 - x * x);
        long long mn = ceil(sqrt((long long)r1 * r1 - x * x));
        ans += mx - mn + 1;
    }

    return ans * 4;
}

---