점 찍기 : https://school.programmers.co.kr/learn/courses/30/lessons/140107#
(x,y)에 대해서 원점부터의 길이는 d^2 = x^2 + y^2
의 공식으로 구할 수 있습니다.
이를 통해서 y가 0일때, x가 d보다 작거나 같을때까지의 점 개수를 구해줍니다.
int a = 0;
while(k*a <= d){
a++;
}
a는 d보다 큰 x의 좌표가 되기때문에 1을 빼주어 마지막 a값을 구해줍니다.
y좌표를 0부터 a까지 반복하면서
최대의 x좌표가 a이기 때문에, 각 y좌표에서 d보다 작거나 같은 x를 a의 값을 줄여가면서 조건을 만족하는 점의 개수를 answer에 저장을 반복해줍니다.
long answer = 0; //점의 개수
a--; //k와 곱해주기 위해 점의 개수에서 1을 빼줍니다.
int y = a*k; //y의 최대값
for(int i=0;i<=y;i+=k){
//현재y좌표 ^ 2 + 현재x좌표(a*l) ^ 2 가 d ^ 2보다 작거나 같은 경우를 찾을때까지 반복
while(Math.pow(i,2) + Math.pow(a*k,2) > Math.pow(d,2){
//a감소
a--;
}
//조건을 만족하는 a를 점의개수를 맞춰주기 위해 1을 더해고 answer에 더해줍니다.
answer += (a+1);
}
a값은 최대 x값보다 작거나 같기 때문에 항상 작아지게 됩니다. 그렇기 때문에 O(NlogN)의 시간복잡도로 해결할 수 있습니다.
통과는 했지만 문제 풀이가 너무 지저분하고 더 나은 풀이가 분명히 있을거라 생각하였습니다.
역시 이전풀이는 너무 직관적으로 생각한 풀이였고 더 나은 풀이가 있었습니다.
y좌표를 k만큼 증가시키면서 d^2 = x^2 + y^2
의 공식에서 해당 y좌표에서 조건을 만족하는 x좌표를 찾기 위해 x^2 = d^2 - y^2
로 변경하여 점의 개수(x/k + 1
)를 찾게 된다면 훨씬 효율적으로 구현할 수 있었습니다.
이러면 O(N)으로 문제를 해결할수 있게 됩니다.
long answer = 0;
//y좌표
for(int y=0;y<=d;y+=k){
//해당 y좌표에서 조건을 만족하는 x
int x = (int)Math.sqrt((Math.pow(d,2)-Math.pow(y,2)));
//해당 x좌표에서 k를 나누고 1을 더해주면 해당 좌표까지의 점 개수를 구할 수 있습니다.
answer += (x/k)+1;
}
class Solution {
public long solution(int k, int d) {
int a = 0;
while(k*a <= d){
a++;
}
long answer = 0;
a--;
int y = a*k;
for(int i=0;i<=y;i+=k){
while(Math.pow(i,2)+Math.pow(a*k,2) > Math.pow(d,2)){
a--;
}
answer += (a+1);
}
return answer;
}
}
class Solution {
public long solution(int k, int d) {
long answer = 0;
for(int y=0;y<=d;y+=k){
int x = (int)Math.sqrt((Math.pow(d,2)-Math.pow(y,2)));
answer += (x/k)+1;
}
return answer;
}
}