[Algorithm] Programmers :: 점 찍기

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

프로그래머스

long long solution(int k, int d)
{
    long long answer = 0;
 
    int maxCol = d - (d % k);
    int count = d / k + 1;
 
    answer += count;
 
    for (int i = k; i <= d; i += k) // y축이동
    {
        int curY = i;
        int curX = maxCol;
 
        while (1)
        {
            int distance = ceil(sqrt(pow(curY, 2) + pow(curX, 2)));
 
            if (distance > d) // 범위 넘으면
            {
                curX -= k; // k만큼 열 줄이고
                --count;
            }
            else
            {
                answer += count;
                maxCol = curX;
                break;
            }
        }
    }
 
    return answer;
}

원점기준으로 반지름d만큼의 원을 그렸을 때, 1사분면에 위치한 원이 포함한 점의 개수를 구하는 문제이다.

점은 k배수만큼만 찍힌다.

 

나는 그냥 0행부터 시작해서 d행까지, y축값을 k만큼 건너뛰면서 이전행에서의 최대열을 그대로 이어받았을 때, d값을 넘어선다면 열값을 k만큼 감소시켰다.

감소시키면서 해당 행에서의 점개수도 1개씩 빼줬고, 유효한 좌표이면 다시 다음 y축값으로 넘어간다. (넘어가기전에 점개수를 answer에 포함시킨다. 점개수도 다음행에 그대로 이어간다)