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

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

using namespace std;

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

 

d의 범위가 크기 때문에 단순 이중 반복문으로 풀면 시간초과가 나는 문제이다.

어차피 좌표의 개수를 알기 위해서는 x나 y값중 하나만 알아도 되기에 x축을 고정시키고 나머지 가능한 y값의 개수를 구하는 방식을 사용한다.

 

먼저 계산식에 따라 x^2+y^2<=d^2이다.

따라서 이는 y^2 <= d^2-x^2가 된다.

우리는 양수 쪽 범위만 필요하고, 최대 값을 찾아서 간격을 나누면 현재 x에 대해 가능한 y 값들을 알 수 있게 된다.

따라서 y = sqrt(d^2-x^2)의 값을 먼저 구해준다.

 

이렇게 구한 y 값은 가능한 y값 중 최대 값이다.

따라서 주어진 간격인 k로 나눠서 가능한 y 값들의 개수를 구한다.

여기서 주의할 점은 좌표가 0일 때도 가능하므로, +1을 하여 이점을 체크해준다.

ex) K=2, d=4, x=0
sqrt(16-0) = 4 = y
가능한 최대 y 값 = 4

나머지 가능한 y 값
0을 체크하기 위해 + 1 추가
(0, 2, 4) -> y/k+1 -> 3