점 찍기

프로그래머스

 

피타고라스의 원리만 알면 풀 수 있는 문제.

 

---

근데, 피타고라스 원리 그대로 반복문을 2번 돌려서 풀면 시간초과가 뜬다.

 

틀린 풀이

def solution(k, d):
    dist = (d ** 2) // (k ** 2)
    
    
    cnt = 0
    same_cnt = 0
    
    i = 0
    while i <= dist:
        j = 0
        while i**2 + j**2 <= dist:
            cnt += 1
            if i == j:
                same_cnt += 1
                break
            j += 1
        i += 1
        
        
    return 2 * cnt - same_cnt

 

이렇게 풀면 시간초과가 뜨므로, 반복문을 한 번만 돌려서 풀 수 있게 풀이를 변경했다.

 

---

풀이 코드

 

def solution(k, d):
    dist = (d ** 2) // (k ** 2) # a**2 + b **2 <= dist
    
    cnt = 0
    
    a = 0
    while a <= dist**0.5: # a의 범위 제한
        max_b = int((dist - a ** 2) ** 0.5) # 위 식에서 b의 최댓값을 구할 수 있다.
        cnt += (max_b + 1) # b의 최댓값까지의 숫자 + 0을 cnt에 더해줘야 하므로 max_b + 1을 더해준다.
        a += 1
        
        
    return cnt

 

이런 식으로 b의 범위를 반복문 한 번으로도 정할 수 있고, 이렇게 풀 경우 시간복잡도가 대폭 감소한다.