프로그래머스 [ LV2 | Python] 점 찍기

링크

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

풀이

아래의 조건에 맞춰 찍을 수 있는 점의 개수를 구해야 하는 수학(?) 문제

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

원점으로부터의 거리를 구하기 위해서 a * k의 제곱과 b * k의 제곱을 더한 값이 d 를 넘지 않을 때 까지 반복문을 통해 값을 1 씩 늘려줬다.

각 k, d의 입력 제한이 1,000,000 이지만 최대가 500,000 라고 생각했고 이는 k 가 0, d가 500000 일 때를 고려하지 않은 시간 복잡도 였다. (따지고 보면 O(500,000^2) 정도 일 것 같다.)

따라서 위의 풀이로는 시간초과를 마주했다.

위의 과정을 통해 하나하나 따져가는 것은 불가능 하다고 생각했고, 공식을 이용하기로 했다.

원점과의 거리를 구하는 공식을 이 문제와 관련지어 생각해볼 경우 다음과 같은 공식을 얻어낼 수 있었다.

• math.sqrt((a*k) + (b*k)) < d

a * k 는 d 와 k를 이용해 다음과 같은 공식으로 최대 값을 얻어낼 수 있다.

• (d // k) * k

따라서 위의 공식을 다음과 같이 수정하여 해결했다.

• b * k < d^2 - a*k (a*k 는 i를 통해서 얻어낼 수 있다)

코드

Python

시도(시간 초과)

import math
def solution(k, d):
    answer = 0
		a = 0
		b = 0
    while math.sqrt((a * k)**2 + (b * k)**2) <= d:
        answer += 1
        if b <= d:
            b += 1
            if a < d and math.sqrt((a * k)**2 + (b * k)**2) > d:
                b = 0
                a += 1
	return answer

정답

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