[C++] 점 찍기

[문제]

코딩테스트 연습 - 점 찍기 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

원의 방정식은 a^2 + b^2 = r^2이니 해당 문제에서는 d가 r을 대체하므로 a^2 + b^2 = d^2이라고 볼 수가 있다.

 

고로 만약 d가 5로 주어지고 k가 1로 주어진 경우라면

 

위의 그림과 같이 x좌표가 0부터 거리 5(d)가 될 때까지 k값만큼 움직이면서 해당 위치에서 원의 방정식을 이용한 y좌표의 정수의 마지막까지를 더할 수 있다는 것을 알 수가 있다.

이는 곧, 수식으로 표현하면

( 제곱근의 가장 큰 y값 / k ) + 1

으로 표현이 가능하다. 참고로 수식에서 마지막에 1을 더하는 이유는 y축이 0일때를 포함해야 하기 때문이다.

이를 이용하면 sqrt로도 쉽게 풀 수가 있지만 나의 경우에는 이분탐색을 이용해서 접근을 하였다. 자세한 내용은 밑의 코드 참고.

[회고]

이전에 풀었던 두 원 사이의 정수 쌍과 비슷한 유형의 문제라서 쉽게 풀 수 있었다.

다만, end값을 처음에는 d가 아니라 k로 뒀다가 1,000,000의 제곱을 절반으로 나눈값이 mid에 들어가서 mid * mid를 할 때, mid가 long long 범위를 넘어선다는 문제가 있다는 것을 발견하고 d로 바꾸었다.

[코드]

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

using namespace std;

long long binary(long long k, long long d){
    long long start = 0;
    long long end = d;
    long long mid = 0;
    long long answer = 0;
    while(start<=end){
        mid = (start + end) / 2;
        if(mid * mid > k){
            end = mid - 1;
        }
        else {
            answer = mid;
            start = mid + 1;
        }
    }
    return answer;
}

long long solution(int k, int d) {
    long long answer = 0;
    long long lk = 0;
    long long ld = 0;
    lk += k;
    ld += d;
    
    for(long long i = 0;i<=ld;i+=lk){
        //y좌표가 0,1,....늘어날때
        
        //x좌표가 1씩 이동할때마다 해당 좌표에서 answer에 n개 추가
        long long len = ld * ld - i * i;
        //len의 제곱근 구하기.
        long long root_len = binary(len, ld);
        //root_len은 제곱근의 가장 큰 정수.
        answer += (root_len / lk) + 1;
    }
    
    return answer;
}