2025.4.9 알고리즘 코드카타

알고리즘 코드카타 - 116. 점 찍기

문제 링크

문제 설명

좌표평면을 좋아하는 진수는 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개 입니다.

오답 코드

#include <string>
#include <vector>

using namespace std;

long long solution(int k, int d) {
    long long answer = 0;
    for(long long i = 0; i*k <= d; i++)
    {
        for(long long j = 0; j*k <= d; j++)
        {
            long long x = i*k;
            long long y = j*k;
            if((d*d) >= (x*x)+(y*y))
            {
                answer++;
            }
        }
    }
    return answer;
}

• 반복문을 통해 문제에서 점이 찍히는 대로 실제 점을 찍어보는 방식
• k와 d의 범위가 충분히 작았다면 위 코드로도 통과할 수 있었을 것이다.
• 하지만 k와 d가 최대 100만인지라 x,y가 엄청나게 커진다. 그러므로 위와 같이 이중for문을 작성하게 되면 시간 초과는 따놓은 당상.

풀이 코드

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

using namespace std;

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

• 시간초과 케이스를 없애기 위해 반복문을 최적화했다.

1. x좌표 자체를 반복문에 넣어서 증가 형태를 x+=k로 하였다.

2. 그리고 for문 내에서는 y좌표만 계산하여 정답에 추가하도록 하였음.

   max_y 와 count_y의 원리

   • max_y는 y의 유클리드 거리이다.
     좌표평면 상에서 원점과 한 점의 거리 d는 $d = \sqrt{x^2+y^2}$ 이므로 여기에 양변을 제곱하여 루트를 벗기고 y를 한 쪽으로 몰면..
     아래와 같이 도출 가능.
     long long max_y = sqrt((long long)d * d - x * x)
     
     변수의 이름이 max_y인 이유는 원점을 기준으로 하는 반지름 d길이의 원을 그렸을 때, x = 4(특정 x) 인 선을 그려보면 원과 만나는 점이 max_y인데, max_y보다 작은 y는 모두 원점에서 거리가 d 이하인 점이기 때문.
   • 위 코드는 x좌표를 구하고, x좌표마다 가능한 y좌표를 모두 구해 정답에 그 개수를 추가하는 식이다.

3. 입력값 d는 경우에 따라 오버플로우가 있을 수 있으므로 d*d를 long long으로 형변환 해주었다. 이것만으로 대부분의 테스트 케이스를 통과할 수 있었다.