[프로그래머스][C++] 점 찍기

점 찍기

문제 링크

점 찍기

분석

원점(0, 0)을 중심으로 x와 y좌표는 0부터 k의 배수인 점들을 찍고, 개수를 구해야합니다.

원점과 거리가 d를 넘는 위치에는 점을 찍지 않는다는 것은 반지름이 d고, 원의 내부에만 점을 찍는다는 것을 의미합니다.

중첩 방복문 등으로 시간복잡도를 $O(n^2)$가진다면 시간 초과가 발생합니다.

x, y는 k의 배수이므로, $x = a * k$, $y = b * k$ 형태로 나타낼 수 있습니다.
원의 조건에 대입하면 다음과 같습니다.
$x^2 + y^2 <= d^2$
$(ak)^2 + (bk)^2 <= d^2$
$k^2 * (a^2 + b^2) <= d^2$
$a^2 + b^2 <= (d/k)^2$

즉, 문제는 아래 조건을 만족하는 a, b의 개수를 세는 것과 같습니다.
$a, b ≥ 0$으로 정수일 때, $a^2 + b^2 <= (d/k)^2$

$d/k$를 먼저 구한 뒤, 그 범위 내에서 가능한 정수 쌍 a, b를 찾으면 됩니다.

풀이

#include <cmath>

using namespace std;

long long solution(int k, int d) {
    long long answer = 0;
    
    // x좌표를 0부터 d까지 k간격으로 증가시키며 반복
    for (long long a = 0; a <= d; a += k)
    {
        // x에서 원의 방정식에 따라 가능한 y의 최대 길이를 구합니다.
        // y^2 <= d^2 - x^2
        long long bSquared = static_cast<long long>(d) * d - a * a;
        // y좌표의 최대 거리까지 k 간격으로 갈 수 있는 개수 계산
        answer += static_cast<long long>(sqrt(bSquared) / k) + 1; // b = 0도 포함
    }
    
    return answer;
}

성능 요약

시간 복잡도는 $O(\frac{d}{k})$입니다.

• 반복문 $O(\frac{d}{k})$
• sqrt함수 $O(1)$
• $O(\frac{d}{k}) + O(1)$

공간 복잡도는 고정된 크기의 상수 공간을 사용하기 때문에 $O(1)$입니다.

테스트 1 〉 통과 (0.01ms, 4.18MB)
테스트 2 〉 통과 (0.01ms, 4.2MB)
테스트 3 〉 통과 (0.02ms, 4.14MB)
테스트 4 〉 통과 (0.01ms, 4.17MB)
테스트 5 〉 통과 (0.02ms, 4.14MB)
테스트 6 〉 통과 (0.02ms, 4.19MB)
테스트 7 〉 통과 (0.02ms, 4.45MB)
테스트 8 〉 통과 (0.14ms, 4.02MB)
테스트 9 〉 통과 (0.02ms, 4.2MB)
테스트 10 〉 통과 (0.04ms, 4.03MB)
테스트 11 〉 통과 (2.95ms, 4.21MB)
테스트 12 〉 통과 (0.01ms, 4.22MB)
테스트 13 〉 통과 (1.46ms, 4.21MB)
테스트 14 〉 통과 (1.04ms, 4.04MB)
테스트 15 〉 통과 (0.01ms, 4.22MB)
테스트 16 〉 통과 (0.01ms, 4.21MB)