[프로그래머스] 점 찍기 / 자바(Java)

문제

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

프로그래머스

 

---

해설

k와 d 모두 최대 1,000,000인 문제라 일일히 2차원 영역의 범위를 계산하면 시간초과가 발생합니다.

그래서 원의 반지름을 이용한 수식으로 답을 구합니다.

원점과의 거리가 d를 넘지 않는 위치에 점을 찍기 때문에 원점에서 d의 반지름을 가진 원 내부에 있는 x,y모두 k의 배수인 점을 구하는 문제가 됩니다.

x의 좌표가 모두 k의 배수이기 때문에 특정 x좌표를 k*i라고 표현할 수 있습니다. 

 

이때의 높이 h를 구하는 공식은 아래와 같이 됩니다.

h^2 = d^2 - (k*i)^2

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

k*i인 시점에 해당되는 점들의 수는 h보다 작은 k의 배수와 같아 h를 k로 나누어 주면 0보다 큰 k의 배수의 수가 나와 +1로 보정해 줍니다.

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

주의점

• 제곱을 할 때 형변환에 신경쓴다.
• y좌표가 0인 경우를 추가해 준다.

---

코드

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