[프로그래머스] 점 찍기 (Python)

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

프로그래머스

 

문제 설명

좌표평면을 좋아하는 진수는 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가 2, d가 4인 경우에는 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍습니다.

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

---

제한사항

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

 

---

 

시간초과 났던 코드

from itertools import product

def solution(k, d):
    answer = 0
    lst = [k*idx for idx in range(d//k+1)]
    limit = d**2
    
    for pro in list(product(lst, repeat=2)):
        if pro[0]**2+pro[1]**2 <= limit:
            answer += 1
            
    return answer

 

정답 코드

import math

def solution(k, d):
    answer = 0
    
    # a의 범위는 0부터 d까지, k씩 건너뛴다.
    for a in range(0, d+1, k):
        # a**2 + b**2 <= d**2
        # b**2 <= d**2 - a**2
        limit = math.sqrt(d**2 - a**2)
        # answer += b의 개수는 limit을 k로 나눈 몫(k씩 건너뛰므로) + 1
        answer += limit // k +1
    
    return answer

 

✏️ 처음에 원점(0, 0)과 (a, b) 사이의 거리를 (a-0) + (b-0)으로 생각했었으나, 답이 아니었다. 원점과 (a,b) 사이의 거리는 둘을 연결한 선의 길이로, 삼각형의 빗변이다.

✏️ 처음 풀이한 방식은 나올 수 있는 수를 담은 리스트를 가지고 순열을 구해서, 원점과의 거리가 d 이하인 조건을 만족하면 answer에 1씩 더해주는 것이었다. 하지만 시간초과가 났다.

✏️ 다른 분들의 코드를 참고해 a를 기준으로 계산하는 방식으로 코드를 수정했다. a**2+b**2 <= d**2 여야 하는 상황이므로, a가 구해진다면 b의 최대치는 d**2-a**2의 제곱근이다. 따라서 그 최대치를 k로 나눈 몫에 1을 더해주면 답이 나온다!