[Lv.2] 점 찍기 - python

프로그래머스

문제설명

좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다.

• 원점 (0,0)으로부터 x축 방향으로 a*k(a=0,1,2,3,…), y축 방향으로 b*k(b=0,1,2,3,…)만큼 떨어진 위치에 점을 찍습니다.
• 원점과 거리가 d를 넘는 위치에는 점을 찍지 않습니다.

정수 k와 원점과의 거리를 나타내는 정수 d가 주어졌을 때, 점이 총 몇 개 찍히는지 return하는 solution함수를 완성하세요.

 

제한사항

• 1 ≤ k ≤ 1,000,000
• 1 ≤ d ≤ 1,000,000

 

풀이

🔥 피타고라스의 정리를 이용하면 쉽게 풀 수 있는 문제입니다.

위의 이미지에서 알 수 있듯이 d와 x만 알면 y의 범위를 알 수 있고, x는 for문을 이용해 점차 증가시킬 수 있습니다.

이때! 주의해야할 점은 (x,y)의 x와 y는 k의 배수만 가능하다는 점입니다.

이렇게 위의 이미지와 피타고라스를 이용해 각 x에서의 y의 범위는 아래처럼 구할 수 있습니다.

n,m = int(d/k),d**2
for i in range(k,d,k):
	# y**2 = d**2 - i**2
    height = int(sqrt(m-i**2))
    answer += int(height / k)

 

코드

from math import sqrt
def solution(k, d):
    answer = 0
    n,m = int(d/k),d**2
    for i in range(k,d,k):
        height = int(sqrt(m-i**2))
        answer += int(height / k)
    return answer + 2*n + 1