[문제 설명]
[문제 이해]
[그림1]
먼저 문제에서 k = 2, d = 4인경우를 생각해보자
a배열은 {0,1,2,3 .....} 어디까지 증가할지 모른다.
a*k로 배열이 구성되면 {0,2,4 .....}
문제로 돌아가서 해석하면 d를 넘지 않아야한다. 그러면 d까지는 증가할수 있다는 것이다. 그래서 범위가 d이하 까지 좁혀진다.
그리고 k만큼씩 증가하므로 증감식에 i+=k를 하였다.
for(int i = 0; i <=d ; i+= k)for문내용을 이해한다.
일단 두점사이의 거리는 유클리드 호제법을 사용한다.
수학적으로 (x1-x2)^2 + (y1-y2)^2 한 값을 루트를 씌운값이 두점사이의거리 값이다.
d와의 거리는 d를 제곱한다. 이때 d의 범위는 1000000이므로 제곱하면 int형범위를 벗어나므로 long타입으로 업캐스팅을 해주어야한다.
long max = (long) d * d;curr는 i지점의 좌표를 의미한다.
i는 k만큼증가할것이다.
그러므로 i = {0,2,4}
curr는 {0,4,16} 이렇게 구성될것이다.
top에서는 제곱한 두점사이의 거리를 측정한다.
ex) 0,0 -> 4,4
2,2 -> 4,4
4,4 -> 4,4
각 실행단계마다 answer += top/k +1 값을 담는다.
그림으로 이해해보자
0,0 지점과 4,4지점 사이를 만족하는 값은 실제로 3개가 존재한다.
그래서 두점사이의 거리 top 에서 k를 나눈다.(빨간색에있는 점들만 찾아야하므로 빨간선들은 k만큼씩 차이로 구성되어 있다).
두점 사이의 거리가 4라고 하면 4/2을 나눈 값에 y절편(curr,0)지점인 +1을 더한다. = >3이 나올것이다. 그림의 파란색 지점들이다.
2,2 지점과 4,4지점을 비교하여 위 방법 처럼구하면
2가 나올것이다. 실제로 의미있는 점은 파란색 점들이다.
마지막으로 4,4지점과 4,4지점을 위방식으로 구하면 1이다. 실제 의미하는 점은 체크된 파란색 지점이다.
[고민했던 과정]
먼저 그림으로 정답을 구한다면
이점들이 정답일 것이다.
빨간줄의 의미는 배열로 생성된 {0,2,4}만을 구분하기 위해 설정했다
이렇게 6가지가 정답일것이다.
하지만 이렇게 구하기 위해서는 i = 0일때 체크, i = 2일때 , i =4일때체크를 해야하는 2중 for문을 구현해야한다.
문제에서 k,d <= 1000,000이하이므로 시간초과가 발생할것이다. 하지만 나는 가지치기를 잘하면 2중 for문도 가능할것이라 생각하여 구현해 봤지만 역시 시간초과 에러가 발생했다.
로직구현
int i = 0;
int index = 0;
for(int j = list2.size()-1; j>= 0;j--){
if(i > list2.size()-1) break;
int x = list2.get(i);
int y = list2.get(j);
long num = (long)Math.pow(x,2) +(long)Math.pow(y,2);
double dist = Math.sqrt(num);
if(dist <= d){
index = j+1;
i++;
j = list2.size()-1;
answer += index;
}
}
개선방법으로 1중 for문으로도 개선했지만 똑같이 시간초과가 발생했다.
(몇개는 정답이 틀렸다)
[전체 소스코드]
public long solution(int k, int d) {
long answer = 0;
// 설계
/**
* [수학]
* d를 넘지 않는다.
* 그러면 d까지만 배열에 넣으면 되지 않을까?
* i+= k : k만큼씩 증가하면 된다.
*
* 주의점 long타입 안에 int * int형을 넣어서는 안된다. => 올바른 코드 long a = (long) b * c;
*
* for문 이해
*
*/
for(int i = 0; i <=d; i+= k) {
long max = d * d;
long curr = i * i;
int top = (int)Math.sqrt(max - curr);
answer += (top/k) +1;
}
return answer;
}