[JS] 두 원 사이의 정수쌍

 

까다롭다면 꽤 까다로운 문제였다. 우선, 원의 특성을 알아야 한다.

 

원을 4분면으로 나누고, 안의 점의 개수를 센 이후 4배를 하면 모든 점의 개수를 알 수 있다. 단, x축이나 y축 중 겹치는 부분은 한 선만 겹치도록 해야지 4배를 해도 정상적으로 점의 개수가 나올 것이다.

 

 

처음에는 이중 for문을 활용해서 모든 좌표를 계산하려고 했었다. 문제 조건이 백만 좌표까지 주어지는데, 이중 for문으로는 당연하게도 시간초과가 발생하였다.

 

따라서 반복문을 한번 쓸 수 있는 방법으로 문제를 해결하였다.

 

 

예시의 경우 r2의 길이가 3, r1의 길이가 2이다.

1사분면의 점의 개수를 세보기로 하고, x축에 겹친 점만 해당하도록 해보자.

 

이때 우리가 세어야 하는 x좌표는 1,2,3이된다.

 

 

우리는 r1,r2의 길이를 알고 있기 때문에 x좌표가 고정된 경우에 r1,r2원의 높이를 계산할 수 있다.

위와같이 말이다. 해당 그림은 x가 1일때 각각의 원에 삼각형을 그렸을때의 높이를 나타낸다.

 

이때 짧은 길이를 l1 , 긴 길이를 l2라고 생각해보면, 

 

해당 두 길이 안의 정수 점을 찾아야 하므로, l1을 올림하고 l2를 버림한 이후 1을 더해주면 해당 사이의 값을 구할 수 있다.

 

같은 방식으로 모든 x좌표에서 의 점의 개수를 계산해준 후, 4배를 해주면 답이 도출된다.

 

 

 

function solution(r1, r2) {
    let ret = 0
    for (let i=1; i<=r2 ; i++){
        let len_r1 = ~~Math.ceil((r1**2 -i**2)**0.5)
        const len_r2 = ~~((r2**2 -i**2)**0.5)
        
        ret += len_r2-len_r1+1
    }
    return ret*4
}

 

 

 

아래부분을 설명하자면, r1 원의 크기가 더 작기 때문에, 길이를 구하고 루트를 씌우면 NaN이 나오는 경우가 생긴다 해당 경우 0으로 처리를 해줘야 하는데, ~~를 붙임으로써 이를 해결하였다.

     let len_r1 = ~~Math.ceil((r1**2 -i**2)**0.5)