[C++] 두 원 사이의 정수 쌍

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/181187

프로그래머스

[문제 풀이]

우리는 원이 각 x축이 정수일때 y축의 높이를 알 수가 있고 이를 이용해서 문제를 풀 수가 있다.

원의 방정식

원의 방정식은 이와 같고 y축의 높이를 생각해보면

y축의 높이

이와 같은 식이 된다.

그렇기에 해당 공식을 이용해서 문제를 풀 것이다.

문제를 풀 때 코테에서 안 썼던 함수(sqrt 안 쓴지 오래 되어서 헷갈린다.) 를 갑자기 쓰는것은 쉬운 일이 아니기에 이분 탐색을 이용해서 y^2 이 a^2 - x^2을 만족하는 y값을 파악하기로 하였다.

즉, y^2 = a^2 - x^2 을 만족하는 y^2 값을 우선 얻고 해당 값이 될 수 있는 가장 큰 정수 y값을 반환함으로서 y값의 최대 정수를 이분 탐색을 통해서 얻어냈다.

 

또한, y가 r1일때는 해당 값이 정수 * 정수라면 1개를 덜 반환함으로서 해당 위치에 있는 점을 추가로 얻어냈다.

이와 같이 구한 모든 값은 1사분면에 있는 점의 숫자이므로 *4를 통해서 모든 점의 숫자를 구했다.

[회고]

상당히 문제가 정답률이 낮을만했던 문제라고 생각한다.

문제를 풀다가 계속해서 어려움을 겪었던 문제들이 몇가지 있었는데

이때 4에서 점이 6개가 나와야 하는데 y - x를 기존으로 하면 8 - 3 => 5가 나온다. 이와 같은 부분이 x가 0일때만 있지 않았던 것을 몰랐던 것이 첫번째 원인이었고

두번째로 이분탐색을 사용할때 start <= end 가 아니라 start < end로 두었다가 오류가 몇번 생겼었다.

[코드]

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

using namespace std;

long long binary(long long axisY, long long r, int dir){
    //r 은 원의 반지름.
    //axisY는 y축의 제곱값이다.
    
    long long answer = 0;
    long long start = 1;
    long long end = r;
    long long middle = 0;
    
    while(start <= end){
        middle = (start + end) / 2;
        
        if(middle * middle > axisY){
            end = middle - 1;
        }
        else if(middle * middle < axisY){
            start = middle + 1;
            answer = middle;
        }
        else if(middle * middle == axisY){
            //dir이 1이라면 1개를 제거해주고 돌려주자.
            //dir이 1일때 middle * middle => Y축이라는건 해당 dir의 끝에 점이 1개 추가로 있다는 의미이다.
            if(dir == 1){
                return middle - 1;
            }
            return middle;
        }
    }
    return answer;
}

long long solution(int r1, int r2) {
    long long answer = 0;
    //long long을 하는 이유는 r1,r2가 최대 1,000,000이라서 제곱을 하면 int값을 넘을 수 있기 때문.
    long long r;
    //y축의 제곱을 담당할 변수
    long long axisY1 = 0;
    long long axisY2 = 0;
    //y^2 = a^2 - x^2이니
    //1. y^2의 값을 얻은 후
    //2. 해당 값이 정수로 몇이 나오는게 최대인지 파악하면 해당 원의 x축에 있는 점을 알 수가 있다.
    
    r = r2;
    for(long long i = 0;i<r2;i++){
        axisY2 = r * r - i * i;
        answer += binary(axisY2,r,2);
    }
    
    r = r1;
    for(long long i = 0;i<r1;i++){
        axisY1 = r * r - i * i;
        answer -= binary(axisY1, r,1);
    }
    
    //사분면이 있으니 4를 곱해주자.
    answer *= 4;
    
    return answer;
}