문제 풀이 아이디어

🚫 브루탈 포스

가능한 모든 a와 b를 탐색하면서 원 안에 들어오는지 탐색하는 방법이 가장 먼저 떠오릅니다. 하지만 k가 최대 1,000,000, d도 최대 1,000,000입니다. 이중 반복문을 사용하면 100% 시간 초과입니다.

✅ 원의 방정식

고등학교 때 배웠던 원의 방정식을 사용해봅시다. 좌표평면 상의 원을 나타내는 방정식은 x^2 + y^2 = d^2입니다. 따라서 x와 d를 알면 y를 구할 수 있습니다. 이를 통해서 x가 a * k일 때 y의 값을 구합니다.

그리고 나서 (x, 0)에서 (x, y)까지 찍을 수 있는 점의 갯수를 구하면 됩니다. (y / k + 1) 해당 작업을 a * k가 d가 될 때까지 (혹은 d보다 커질 때까지) 반복하면 됩니다.

코드

import Foundation

func solution(_ k:Int, _ d:Int) -> Int64 {
    var ans = 0
    
    for x in stride(from: 0, to: d + 1, by: k) {
        let y = Int(sqrt(Double(d * d - x * x)))
        ans += y / k + 1
    }
    
    return Int64(ans)
}