[프로그래머스] 점 찍기 - 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

입출력 예

 

---

수학 파트.

처음에는 (a*k, b*k) 좌표가 d 범위 내에 있는 지 x, y좌표 각각 체크하는 방향으로 접근하려 했으나 k의 제한 범위가 100만이라 2중 반복문을 사용하면 안될거같아서 다른 방법을 찾아봐야 했다.

근데 다 풀고 남의 코드 보는데 C++로는 2중 for문 적당히 사용하면 되는거같긴했음

 

위의 그림과 같이 한 축의 좌표를 고정하고, 다른 축에서 최대 좌표를 구하여 그 지점부터 몇 개의 점이 들어갈 수 있는지 개수를 세어 모두 더해주기만 하면 된다. 이 때, a와 b가 모두 0일때도 포함이므로 마지막에 1을 더해준다. 따라서 전체 수식은

 

$$ x=i, \\ y=\lfloor{\sqrt{d^2-x^2}}\rfloor$$

와 같이 설계한 뒤, 간격이 k일 때의 점의 개수를 $y/k + 1$ 와 같이 계산해주면 끝

 

인데, d와 k의 범위가 1,000,000이다 보니 다시 한 번 유의해아 할 것은 y의 좌표를 구하는 과정에서 d*d나 x*x의 값이 int 범위에서 overflow가 발생할 수 있으니 타입캐스트를 해줘야 한다....

그거때문에 한번 틀렸다ㅠ

 

int x = i; 부분 안지우는거 까먹었다

 

코드

#include <string>
#include <vector>
#include <cmath>

using namespace std;

long long solution(int k, int d) {
    long long answer = 0;
    
    for(int i = 0; i <= d; i += k) {
        int x = i;
        int y = floor(sqrt((long)d * d - (long)i * i));
        
        answer += y / k + 1;
    }
    return answer;
}