[파이썬]programmers: 점 찍기

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

프로그래머스

---

1. 초기 설계 구현

2차원 배열을 절반으로 나눈 뒤, 값을 구하고 *2를 하여 값을 도출 할 생각을 하였다. 하지만 시간초과 4개...

 

초기구현 코드는 O((N**2)/2)이 되므로 해당 문제에서 원하는 시간을 구해낼 수 없음...ㅠㅠ

def solution(k, d):
    answer = 0
    start = 0
    cnt = 0
    for y in range(start,d+1,k):
        if y >=1:
            start += k
        for x in range(start,d+1,k):
            if (y**2 + x**2)**0.5 > d:
                break
            if y != x:
                answer +=1
            else:
                cnt +=1
    answer *=2
    return answer + cnt

---

이것저것 찾아보다가 구 면적안에 들어가지 않으면 된다는걸 알게되었고, 이를 구현하기 시작!

def solution(k, d):
    answer = 0
    for x in range(0, d+1, k):
        y = (d**2 - x**2)**0.5
        answer += y//k + 1
    return int(answer)

이러면 O(N)의 시간으로 대폭 단축되고, 코드도 훨씬 간결해 짐!

 

알고리즘은 딱히 없었고, 수학적인 내용만 들어있는 문제 였음!