[Programmers] 두 원 사이의 정수쌍(LV.2)

풀이 소요시간 : 측정 안함

문제 풀이는 쉬웠으나 타입캐스팅 오류로 고난을 겪었다. 이전에 풀었던 점 찍기 문제와 유사했다. R 값과 X 값을 고정시키고 그에 맞는 Y 값의 갯수를 구함으로써 O(N) 의 시간복잡도로 풀이할 수 있다.

N 의 크기가 1,000,000 이라 O(N^2) 복잡도로는 풀이할 수 없다는 것을 알 수 있었다.

전체 코드

long long 타입캐스팅 앞으로 유의하자

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

using namespace std;

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

    for(long long X = (-1) * r2; X <= r2; X++) {

        long long High, Low;

        long long R2 = (long long)r2*r2;
        long long R1 = (long long)r1*r1;

        if(R2 - X * X <= 0) {
            High = 0;
        } else {
            High = floor(sqrt(R2 - X * X));
        }

        if(R1 - X * X <= 0) {
            Low = 0;
        } else {
            Low = ceil(sqrt(R1 - X * X));
        }



        if(High == 0 && Low == 0) {
            answer += 1;
            continue;
        }

        if(High != 0 && Low == 0) {
            answer += (High * 2 + 1);
            continue;
        }

        answer += (High - Low + 1) * 2;
        continue;


    }


    return answer;
}