Level 2. 점 찍기

Level 2. 점 찍기

 

 

첫 번째 시도에서는 모든 경우의 수를 계산하느라 시간 초과가 발생했다.

 

// 이 풀이는 시간 초과가 발생한다.
#include <iostream>
#include <cmath>

using namespace std;

long long solution(int k, int d)
{
    long long answer = 0;
    double sqrD = pow(d, 2);

    for (int i = 0; i <= d; i += k)
        for (int j = 0; j <= d; j += k)
            if (pow(i, 2) + pow(j, 2) <= sqrD)
                ++answer;

    return answer;
}

 

사실 for문은 x, y 둘 중 하나에 대해서만 수행해도 된다.

 

x² + y² ≤ d²을 만족하는 쌍을 찾아야 하는데, d는 상수이기 때문에 x를 고정시키면 해당 x 값에서 가능한 y 좌표의 개수를 바로 구할 수 있다.

 

#include <iostream>
#include <cmath>

using namespace std;

long long solution(int k, int d)
{
    long long answer = 0;
    double sqrD = pow(d, 2);

    for (int i = 0; i <= d; i += k)
        ++answer += (long long)(sqrt(sqrD - pow(i, 2))) / k;

    return answer;
}