문제
문제 설명
좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수
k,d가 주어질 때 다음과 같이 점을 찍으려 합니다.
- 원점(0, 0)으로부터 x축 방향으로
a*k(a = 0, 1, 2, 3 …), y축 방향으로b*k(b = 0, 1, 2, 3 …)만큼 떨어진 위치에 점을 찍습니다.- 원점과 거리가
d를 넘는 위치에는 점을 찍지 않습니다.예를 들어,
k가 2,d가 4인 경우에는 (0, 0), (0, 2), (0, 4), (2, 0), (2, 2), (4, 0) 위치에 점을 찍어 총 6개의 점을 찍습니다. 정수k와 원점과의 거리를 나타내는 정수d가 주어졌을 때, 점이 총 몇 개 찍히는지return하는solution함수를 완성하세요.제한 사항
- 1 ≤
k≤ 1,000,000- 1 ≤
d≤ 1,000,000입출력 예
k d result 2 4 6 1 5 26 입출력 예 설명:
- 입출력 예 #1
- 본문의 예시와 같습니다.
- 입출력 예 #2
- (0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (3, 0), (3, 1), (3, 2), (3, 3), (3, 4), (4, 0), (4, 1), (4, 2), (4, 3), (5, 0) 위치에 점을 찍을 수 있으며, 총 26개입니다.
1차 풀이
원점과의 거리라는 표현과, (0,0)부터 (3,4)의 대각선으로 표현되는 다이렉트 거리 5로 계산해야 한다는 것을 보고 바로 피타고라스의 정리가 떠올랐다. 그런데 테스트를 해본 결과 몇 개는 통과되었지만 대부분 시간이 초과되었다.
class Solution {
public long solution(int k, int d) {
return getCount(k,d);
}
// 점까지 계산
private int getCount(int times, int max){
int result = 0;
for(int i = 0; i <= max; i+=times){
for(int j = 0; j <= max; j+=times){
double temp = getDistance(i, j);
if(temp <= max * max){
result++;
}
}
}
return result;
}
// 피타고라스 정리를 이용한 (0,0)부터의 대각선 거리
private double getDistance(int a, int b){
return a*a + b*b;
}
}
2차 풀이
고민을 해보았는데 답이 찾을 수 없어서 결국 풀이를 찾아보았다. 다들 원의 방정식을 사용해서 결과를 도출하였다. 그런데 왜 사용했고 어떤식으로 로직이 흘러가는지에 대해 흐름에 대한 자세한 설명을 해주신 분이 없었다. 이해가 필요했기에 천천히 한 단계씩 고민을 해보았다.
원의 방정식이 뭔가?
원의 중심이 (a, b)이고 반지름이 r인 원의 방정식은 \((x - a)^2 + (y - b)^2 = r^2\) 이다.
원의 방정식이 어떤 용도로 사용되었는가?
과정 하나하나에 추론을 통해 얻어낸 결과는 다음과 같다. 원의 방정식을 사용한 결정적인 이유는 시간복잡도를 줄이기 위해 2개의 반복문을 1개로 줄이기 위해서 수학적인 스킬을 사용하는 것이다.
반복문을 1개로 줄이기 위한 전반적인 흐름
- (0,0)으로부터 최대거리에 해당하는 거리(지점)을 받는다. (1/4 원의 모습, 방사형의 테두리 부분을 구할 수 있다.)
- 원의 방정식을 변형하면 그 지점들 중 x가 n일때의 y의 값을 구할 수 있다.
- x를 기준으로 반복문을 돌리면 점들의 개수를 구할 수 있다.
과정에 대한 설명
예시의 기준으로 최대 거리가 4로 가정하고 원점(0,0)에서 최대 거리에 있는 점의 위치(x,y)를 구하는 공식을 구해보자.
- 기본적인 원의 방정식
- \[(x - a)^2 + (y - b)^2 = r^2\]
- 원점을 대입한 원의 방정식
- \[(x - 0)^2 + (y - 0)^2 = x^2 + y^2 = r^2\]
- \(y\)의 값을 구하기 위해 먼저 \(x^2\)을 이항해주면
- \[y^2 = r^2 - x^2\]
- \(y\)의 제곱을 없애주기 위해서 루트를 씌워준다.
- \[y = \sqrt{r^2 - x^2}\]
- 최대 거리가 4를 대입한다.
- \[y = \sqrt{16 - x^2}\]
- 이 공식을 사용하면 \(x\)에 대응하는 \(y\)의 값을 값을 파악할 수 있다.
- 0일때 4
- 1일때 \(\sqrt{15}\) (3.n)
- 2일때 \(\sqrt{12}\) (3.n)
- 3일때 \(\sqrt{7}\) (2.n)
- 4일때 0이라는 \(y\)
- \(x\)를 고정할때 \(y\)의 위치로 점의 개수 구하기
- (0,2)일때 가능한 점은 3개 (0,0), (0,1), (0,2)
- (1,2)일때 가능한 점도 3개 (1,0), (1,1), (1,2)
- (1,4)일떄 가능한 점은 4개 (1,0), (1,1), (1,2), (1,3), (1,4)
- 고로 가능한 점의 개수는 \(x\)가 고정일때 \(y + 1\)개와 같다.
- 점의 개수 구하기
- 위의 결과로 \(y+1\)이 점의 개수임을 알았으니 최대거리가 4일때 \(x\)가 0부터 4까지 5,4,4,3,1이 된다.
- 하지만 문제의 예시에서는 2의 배수로 점이 찍힌다고 했으니 다시 계산해야한다.
- 다시 계산을 시작해보자. \(y\)에 \(k\)배 곱해진 위치에서 점의 수를 구해야하니 \(k\)배 곱해준다.
- \[k * y = \sqrt{r^2 - x^2}\]
- \[y = \sqrt{(r^2 - x^2)} / k = \sqrt{16 - x^2} / 2\]
- \(x\)가 0,2,4(<=최대거리, \(k\)의 배수) 일때 2, 1.~, 0가 나오게 되고 \(y\)의 개수는 3, 2, 1 이므로 총 6이 된다.
- 증명이 되었다.
코드로 작성하기
class Solution {
int d = 4;
int k = 2;
public long solution(int k, int d) {
return getCount(k, d);
}
private long getCount(int times, int distance) {
long cnt = 0;
for (long x = 0; x <= distance; x += times) {
long y = getCountFromX((int) x, distance) / times;
cnt += y + 1;
}
return cnt;
}
private long getCountFromX(int x, int distance) {
return (long) Math.sqrt((double) Math.pow(distance, 2) - (double) Math.pow(x, 2));
}
}