Level2️⃣ - 점 찍기

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

프로그래머스

문제 접근

두 점 사이의 거리 공식을 활용해서 문제를 해결하고자 했다.

 

function solution(k, d) {
    let ret = 0;
    for(let x = 0; x <= d; x+=k){
        for(let y = 0; y <= d; y+=k){
            let a = Math.sqrt(x**2 + y**2);
            if(a <= d) ret++; 
        }
    }
    
    return ret;
}

 

하지만 시간초과가 나왔다. 최악의 경우에 O(N^2)이기 때문이다.

이중for문을 사용하지 않고 구현하는 방법을 고민하다가 다른 블로그의 풀이를 참고했다.

 

x가 0, 1, 2, 3 ... 하나씩 증가할 때마다 최대한 찍을 수 있는 y축의 갯수를 구하면 된다.

이걸 어떻게 구할 수 있냐면 바로 두 점 사이의 거리 공식을 활용하면 된다. 

원점으로부터 (x, y)까지의 거리를 d라고 표현할 때 다음과 같이 표현할 수 있다.

x^2 + y^2 = d^2

y^2 = d^2 - x^2

 

그리고 y^2에 제곱근을 씌우고 k로 나누어주면 최대한 찍을 수 있는 y축의 점의 갯수를 구할 수 있다.

단, 여기서 1을 더해주어야하는데 왜냐하면 x에 찍은 점의 갯수도 포함해야하기 때문이다.

function solution(k, d) {
    let ret = 0;
    for(let x = 0; x <= d; x+=k){
        let yCnt = Math.floor(Math.floor(Math.sqrt(d**2 - x**2))/k) + 1;
        ret += yCnt;
    }
    
    return ret;
}