점 찍기(프로그래머스) 문제풀이

문제 

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

프로그래머스

 

 

 

문제 접근 방식

1사분면(x,y축 포함)에 k 단위로 점을 찍고, 원점으로부터의 거리가 d 이하인 점의 개수를 구하는 문제이다. 특정 거리 d 이내에 있다는 것을 보고 2차원 좌표공간에서 원을 떠올렸고, 원의 방정식을 활용해서 문제를 풀었다.

 

k의 배수( 0, k, 2k, ...) 에 해당하는 것을 x값으로 설정하고 이를 원의 방정식에 대입하여 y 좌표를 구한 후, 이를 내림 후 k로 나눈 나머지를 통해 x= nk 상에 존재하는 점의 개수를 구한다. 모든 x=nk 상의 점들을 누적해서 반환하면 된다.

 

시간 복잡도

x= d 이하의 값 중 k배수의 값들만 순회하기 때문에 O(d/k) 번 순회를 하며, 최댓값이 1e6이므로 시간내에 동작한다.

 

코드

from math import floor,sqrt
def solution(k, d):
    answer = 0
    for x in range(0,d+1,k):
    
    	#원의 방정식을 통해 y값을 구한다.
        y=int(floor(sqrt(d**2-x**2)))
        
        # x=nk 위에 존재하는 y 값 중 k의 배수만을 카운트 한다.
        answer+=y//k+1

	return answer