[문제설명]
좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다.
원점(0, 0)으로부터 x축 방향으로 ak(a = 0, 1, 2, 3 ...), y축 방향으로 bk(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
[나의 풀이 (1차)]
class Solution {
public long solution(int k, int d) {
long answer = 0;
for (long i = 0; i <= d/k; i++) {
long x = i * k;
for (long j = 0; j <= d/k; j++){
long y = j * k;
if (Math.sqrt(Math.pow((double) x, 2) + Math.pow((double) y, 2)) <= d) {
answer++;
// System.out.println("i : "+ i + " j : " + j + " answer : " + answer);
}
}
}
return answer;
}
}단순하게 풀이해본 코드이다. 각각의 좌표를 증가시키면서 원점까지의 길이보다 작을때만 answer를 증가시켜주었다. 그러나, 제한사항을 보면 k와 d가 각각 1000000까지 가능하다고 하였다. 위 코드를보면 2중 반복문을 쓰기 때문에 최악의 경우 k=1이고 d=1000000일 경우 O(1000000 x 1000000) 까지 걸릴 수 있는 정신나간 효율성을 보여준다.
당연히 폐기해야하는 코드이다.
[나의 풀이 (2차)]
class Solution {
public long solution(int k, int d) {
long answer = 0;
for (long i = 0; i <= d/k; i++) {
long x = i * k;
long y = (long) Math.sqrt((long) Math.pow(d, 2) - (long) Math.pow(x, 2)) / k;
answer += y + 1; // 0도 포함해주어야 하므로 +1
}
return answer;
}
}문제를 다시 생각해보자, 문제에서는 원점과 찍은 점의 거리가 d이하인 양의 정수인 점의 개수를 구하는 것이다. '양의 정수'라는 제한 조건을 버려두고, 위의 조건을 만족하는 무수히 많은 실수 좌표의 점들을 다 찍어보면 해당 점들은 아래와 같은 식을 만족한 다는 것을 알 수 있다.
(원의 방정식)
x^2 + y^2 <= d^2 (x >= 0, y >= 0)
위의 방정식을 토대로 우리는 하나의 점을 기준으로 다른 점을 찾을 수 있다.
따라서, 기존 풀이와 같은 2개의 반복문을 1개의 반복문으로 줄일 수 있을 것이다.
아래와 같이 원의 방정식을 변형해서 y의 개수를 구할 수 있다.
long y = (long) Math.sqrt((long) Math.pow(d, 2) - (long) Math.pow(x, 2)) / k;for문을 통해서 x점을 하나 선택하고 제곱해서 d의 제곱에서 빼주고 제곱근을 취한다. 이때, 어쨌든 y의 타입이 long타입이므로 정수부만 y에 저장되게 된다.
(ex : y^2이 12이더라도, y에는 3 저장)
이때 y는 0도 가능하므로 y + 1을 answer에 더해주면 끝이다.
아래는 채점결과이다.
