[프로그래머스] 점 찍기 - C++

문제 설명

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

---

x좌표(=> ak)를 고정시켜 놓고 y(=> bk) 값의 최댓값을 찾은 다음 (bk/k) + 1 개를 ans에 더하면 된다.

ak = 0 일 때부터 bk의 값을 찾는다. bk를 k로 나눈 나머지를 bk에서 빼면 시작점을 구할 수 있다.

이후 bk를 찾는데에 두 가지 방법을 사용할 수 있다.

1. ak를 k 만큼 증가시킨 후 bk에 k를 감소해 가며 적절한 값 찾기.

-> 결국 ak와 bk는 독립적으로 증감하기 때문에 최대 2백만 회 소요되어 시간제한에 걸리지 않는다.

2. sqrt를 활용하여 d*d - ak * ak의 루트값 구하기. 

 

다만 백만 * 백만은 int 범위를 넘어감으로 ak와 bk를 long long으로 처리해야 한다.

 

---

소수점 연산인 sqrt를 사용하는데 거리낌이 있어 제곱을 사용해서 풀었다. 다만 k 가 d 보다 큰 경우를 처리하지 않아 1번 방식을 사용했을 때는 무한 루프가 걸렸다. 또한, 제곱 연산에서 int overflow가 일어났다. 이 두 개를 고치니 통과할 수 있었다! 틀렸다면 알고리즘 의심과 함께 곱셈 연산을 잘 살펴봐야겠다