코딩 테스트 [프로그래머스] - 점 찍기

문제 링크

원점과 특정 점(x, y) 간의 거리 d는

• $d^2$ = $x^2$ + $y^2$

인 점을 이용해 문제를 풀었다.

---

전체 코드는 다음과 같다.

import java.util.*;

class Solution {
    public long solution(int k, int d) {
        long answer = 0;
        
        long dd = (long)d * d;
        
        for(int i = 0; i <= d; i += k){
            long xx = (long)i * i;
            
            answer += (long)Math.sqrt(dd - xx) / k + 1;
        }
        
        return answer;
    }
}

---

최대 거리 d의 제곱을 구해 dd에 저장했다.

        long dd = (long)d * d;

한 점의 특정 좌표를 $x$로 가정하면, $x$는 a * k이고, a는 0 이상의 정수이다.
$x$가 될 수 있는 경우는 다음의 반복문의 i로 나타낼 수 있다.

        for(int i = 0; i <= d; i += k){
            ...
        }

한 점의 특정 좌표($x$)의 제곱을 구해 저장한다.

        for(int i = 0; i <= d; i += k){
            long xx = (long)i * i;
            
            ...
        }

최대 거리의 제곱에서 특정 좌표($x$)의 제곱을 뺀 값에 루트를 하면
나머지 좌표($y$)의 최대값을 알 수 있다.

(long)Math.sqrt(dd - xx)

나머지 좌표($y$)는 b * k 로 나타날 수 있고 b는 0 이상의 정수이다.

나머지 좌표($y$)의 최대값을 k로 나누면 b 나올 수 있는 자연수의 경우를 구할 수 있고, 여기에 0인 경우를 더하면 b가 나올 수 있는 모든 경우를 구할 수 있다.

        for(int i = 0; i <= d; i += k){
            long xx = (long)i * i;
            
            answer += (long)Math.sqrt(dd - xx) / k + 1;
        }

$x$의 모든 경우의 수마다 각 $y$의 경우의 수를 모두 더하면 정답이 된다.

        for(int i = 0; i <= d; i += k){
            long xx = (long)i * i;
            
            answer += (long)Math.sqrt(dd - xx) / k + 1;
        }
        
        return answer;