점찍기

내코드

def solution(k, d):
    answer = 0
    cnt_b=0
    cnt_s=0
    cnt=1
    d_=(d+1)**2

    for i in range(0,d_):
        cnt_s+=1
        if cnt_s==(d+1):
            cnt_b+=1
            cnt_s=0

        b=cnt_b*k
        s=cnt_s*k 
        if s**2+b**2>d**2:
            continue
        cnt+=1
    
        
    return cnt

위코드의 원리는 값을 차례대로 올려주는 방식을 사용한다.그리고 일정량이상의 값이 되면 B값을 올리고 S값을 0으로 초기화를 한다.

이런방식으로는 이중반복문을 피했으나 시간초과가 걸렸다.그래서 다른사람의 코드를 보았다

 

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

다른점은 두가지이다.

첫번째로는 range에 K값을 넣어서 반복횟수를 /K만큼 줄어든다.

어차피 나는 곱하는 형태였기에 이런방식을 통해도 값은 똑같이 나온다.

대신 시간복잡도를 조금이라도 줄일수 있다.

두번째는 피타고라스를 사용했다는 점이다.

X값정해져있을 경우 Y값이 나올수있는 경우의 수를 전부 구하면된다.

그래서 ( y² = r² - x²)공식을 이용한다.

그렇게 Y값을 구한뒤 숫자에서 k만큼 나눈후 +1한것이 Y값이 나올수있는 모든 경우의 수이다.

예를들어 값이 x가 2고 d가 4 K는 2이라고 가정하자

 

그러면 max_y는 2이다.피타고라스를 이용하면 쉽게 구할수 있다.

이렇게 되면 2가 나타날수있는 수중 가장 큰 수이다.그러면 K는 2이기때문에 나올수있는 수는 0과 2뿐이다.

2/k은 1이다. 그리고 0을 생각해서 +1을 하면 결과가 2가 나올것이다.