[programmers] lv.2 점 찍기

문제 바로가기

문제 접근

1. while문을 두 번 사용해서 모든 k의 배수에 대해서 확인 >> 당연히 시간초과 발생
2. 가능한 x값들 내에서만 모든 k의 배수에 대해서 확인 >> 시간 줄어들었으나 여전히 시간초과
3. 가능한 x값들 내에서의 y값을 구하고 그 값의 범위 내에서의 k에 대한 배수의 개수를 count

정답 코드

3번 접근

def solution(k, d):
    cnt = 0
    x = [i*k for i in range((d//k)+1)] # 가능한 x좌표
    y = [(d**2-dx**2)**(1/2) for dx in x] # x좌표에 따른 y좌표
    for i in y:
        cnt += i//k # y좌표보다 작은 k의 배수
    cnt += len(y) # y=0일 때의 점들 합하기
    return cnt

딱히 새로운 접근법을 요구하지 않는 간단한 구현 문제

다른 사람 코드

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

• y값을 구하고 바로 cnt를 update하면서 더 시간절약 가능