프로그래머스 점 찍기 [Lv. 2] (C++)

프로그래머스

k와 d를 입력 받습니다. 원점 (0, 0)을 기준으로 점을 찍을 때, 원점에서 점의 위치까지의 거리가 d 이하이면서, x % k == 0 && y % k == 0인 점의 개수를 구해주세요.

 

풀이 방법

이진 탐색을 사용하여 풀었습니다. 

Y를 0 ~ d 까지 순회하여 점을 찍을 수 있는 x의 최대 값이 어디인지 구했습니다.

for(long long y = 0; y <= d; y += k)
{
    int start = 1, end = d, ret = 0;
    while (start <= end)
    {
        long long x = (start + end) / 2;
        if (x*x + y*y <= length){

 

이후 구한 x의 크기에 k를 나눈 값을 answer에 더해주어 마무리 했습니다.

answer += ret/k + 1;
// ret = 6 , k = 2일 경우 0, 2, 4, 6 이기 때문에 +1을 해주었습니다.

 

 

사실 length와 y값이 정해져 있는 상황이기 때문에 더 간단하게 풀 수도 있습니다.

수식을 약간 변경해주면 x의 최대값을 한번에 구할 수 있습니다.

x*x + y*y = length  ->  x*x = length - y*y

for(long long y = 0; y <= d; y += k)
    answer += (long long)sqrt(length - y*y) / k + 1;

 

정답 코드

#include <string>
#include <vector>
#include <cmath>
using namespace std;

long long solution(int k, int d)
{
    long long length = (long long)d * d;
    long long answer =0;
    
    for(long long y = 0; y <= d; y += k)
        answer += (long long)sqrt(length - y*y) / k+1;
    
    return answer;
}

 

 

#include <string>
#include <vector>
#include <cmath>
using namespace std;

long long solution(int k, int d)
{
    long long length = (long long)d * d;
    long long answer =0;
    
    for(long long y = 0; y <= d; y += k)
    {
        int start = 1, end = d, ret = 0;
        while (start <= end)
        {
            long long x = (start + end) / 2;
            if (x*x + y*y <= length){
                start = x + 1;
                ret = x;            
            }
            else
                end = x - 1;
        }
        answer += ret/k + 1;
    }
    
    return answer;
}