[알고리즘][KOTLIN] 점찍기

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

프로그래머스

문제 풀이

1. 두 좌표 간의 거리를 구하는 공식을 이용 한다. X^2 + Y^2 = D^2

2. X, Y 를 k 만큼 증가하여 탐색한다.

3. 이때 이중 For 문으로 탐색을 할 경우 시간 초과가 발생한다.

4. 1번의 거리 식에서 Y^2 = D^2 - X^2 이 된다.

5. 4번에서 나온 Y값 중 k 배수가 될 수 있는 개수를 구한다.

코드

class Solution {
    fun solution(k: Int, d: Int): Long {
        var answer: Long = 0
        
        for (a in 0..d step k) {
            val y = getY(d, a)
            // 구해진 y 값 중 k 배수의 개수를 구한다.
            // 0은 무조건 포함되기 때문에 구해진 k 배수의 개수에서 1을 더한다.
            answer += (y / k) + 1
        }
        
        return answer
    }
    
    // y^2 = d^2 - x^2 공식을 이용하여
    // y 값을 구한다.
    private fun getY(d: Int, x: Int): Int {
        val dd = d * d.toLong()
        val xx = x * x.toLong()
        val result = Math.sqrt(dd - xx.toDouble())
        return result.toInt()
    }
}