📗 점 찍기

프로그래머스

import math

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

왜 이렇게 풀었을까?

필요한 사전 지식

• 피타고라스 정리, 완전 탐색 최적화하는 방법(이중 for문을 단일 for문으로)

이 문제로부터 구현력 기르기

• 특정 x값에 대해 가능한 최대 y값을 피타고라스 정리를 활용하여 계산하였습니다.
• int(y // k) + 1로 계산한 것은 y축에서 k 간격으로 점을 찍었기 때문에 k로 나눠주고 원점을 포함하기 위한 1을 더해줬습니다.
• 처음에는 모든 점을 탐색하는 완전 탐색으로 진행했지만, 당연하게도 조건에 막혀 유효한 점만 확인하는 최적화를 진행하게 되었습니다.

이 문제로부터 연상력 기르기

• 문제에서 주어진 조건은 원점에서 점까지의 거리가 d보다 작거나 같음을 만족해야 했고, x, y 좌표가 각각 k의 배수로만 이동할 수 있다는 것이었습니다.
• 좌표가 이렇게 이산적이라는 특징을 지니고 있어서 완전 탐색으로 셀 수도 있겠다!! 싶었지만, k와 d의 범위가 1,000,000까지였으므로 x 좌표, y 좌표 각각 이중으로 돌리기는 힘들겠다는 판단이 섰습니다.
• 그래서 '하나를 기준으로 잡고 나머지를 돌리면 단일 for문으로도 해결할 수 있겠구나' 해서 생각한 방식이 x 좌표를 돌리고 그 안에서 y 좌표의 최대 개수를 구하는 방법이었습니다.