[TIL #29] 점 찍기

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

프로그래머스

 

변의 길이가 ``d``인 정사각형에 ``k``의 간격으로 점을 찍는 문제.

 

최초 접근은 피타고라스 정리를 매 사이클마다 계산하지 않고 $\sqrt{2} ≒ 1.414...$를 활용하려고 했다.

이러면 숫자가 커질수록 발생하는 오차를 말끔히 해결할 수 없다는 걸 깨닫고 선회.

 

다음 방법은 이것.

function solution(k, d) {
    let count = 0;
    const dSquared = d * d;

    // x를 0부터 d까지 k 단위로 순회
    for (let x = 0; x <= d; x += k) {
        // yMax^2 <= d^2 - x^2
        const yMaxSquared = dSquared - (x * x);

        // y의 최대값을 k 단위로 조정
        const yMax = Math.floor(Math.sqrt(yMaxSquared) / k) * k;

        // y가 0부터 yMax까지 k 단위로 증가하는 경우의 수를 더함
        count += (yMax / k) + 1;
    }

    return count;
}

코드가 심플하고 효율이 꽤 괜찮다.

피타고라스를 사용해야 하는 점이 아쉽지만 어쩔 수 없는 것 같다.

 

결과 카운팅에 ``(0, 0)``이 포함된다는 점과, 피타고라스 정리를 사용해야 한다는 점만 떠올리면 간단한 문제.

좌표 평면의 점에 대하여 영역을 계산한다던가 회전한다던가 그런 것만 해봤었는데,

간단해 보이는 유형이라 뭔가 함정이 있지 않나 고민을 좀 했었던 것 같다.

 

이제 보니 이거 레벨 2다...

함정도 없었는데...

대체 왜?