[프로그래머스] 점 찍기

문제

좌표평면을 좋아하는 진수는 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

---

a와 b의 가능한 모든 경우에 대해 x(= a* k), y(=b*k)를 구해주고 해당 x,y좌표가 d를 넘지 않는지 일일히 연산해주는 방법으로 간단하게 풀 수 있을거라 생각할 수 있지만 이러한 방법은 시간초과가 발생한다.

따라서 가능한 점의 개수를 구하기 위한 수식을 생각해 내야한다.

 

1)종료조건( a*k <= d)

먼저 a*k가 d보다 작거나 같은 경우로 종료조건으로 걸어주었다.

k와d는 고정값이기 때문에 a를 0부터 1씩 증가시켜주면 종료조건에 의해 가능한 a의 후보군은 유한집합이 된다.

a*k인 x좌표 만으로 이미 d를 넘어버린다면 어떠한 b즉 y값을 선택해도 조건을 만족하는 점(x,y)을 찾을 수 없기 때문이다.

문제의 예시 k = 2, d = 4의 경우로 살펴보면 a는 0~2의 범위를 갖게 된다는 것을 알 수 있다.

 

2)수식

가능한 a의 후보군을 유한집합으로 만드는데 성공했으므로

이제 각 x값에 따른 가능한 y값의 개수를 구하는 수식을 찾으면 된다.

피타고라스의 정리를 이용하면 원점과 점(x,y) 간의 거리를 쉽게 찾을 수 있다.

이를 d에 대한 수식으로 정리하면

sqrt(x^2 + y^2) <= d*2이 되고 y에 대한 수식으로 다시 정리하면

y <= sqrt( d^2 - x^2)이 된다.

다시 문제의 예시를 통해 살펴보자.

a가 0일 경우 x(x= a*k 이므로)는 0이 되고 위 수식에 의해 (y <= sqrt( 4^2 - 0) -> y <= 4)

가능한 y의 후보군은 0, 1, 2, 3, 4가 된다.

하지만 y = b*k를 만족해야 하므로 위 후보군을 모두 채택할 수 없고 y값은 0과 k의 배수만 채택이 가능한다.

따라서 가능한 y는 0, 2, 4 으로 총3개이다.

이를 로직으로 구현하면 yCnt = 4 / 2(k) + 1가 된다. 4/k 는 k의 배수의 개수이고 +1은 0을 포함 시키기 위함이다.

 

#include <string>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
int a, b;
ll  x, y;

long long solution(int k, int d) {
    ll answer = 0;
    while (a * k <= d ) {
        x = a * k;
        ll bLimit = sqrtl((long double)d * d - (x * x));
        ll yCnt = bLimit / k +1;
        answer += yCnt;
        a++;
    }
        return answer;
}

 

주의해야 할 점으로 sqrt가 아닌 sqrtl을 사용해야 한다는 것이다.

d의 최대 범위가 1,000,000이므로 d^2은 최대 1,000,000,000,000가 될 수 있기 때문이다.

마찬가지로 x,y 또한 int의 범위를 벗어날 수 있기 때문에 long long 타입으로 지정해 주어야 한다.