점찍기 Level2

https://school.programmers.co.kr/learn/courses/30/lessons/140107?language=csharp

프로그래머스

이 문제를 푸는데 있어서 아이디어가 대단한 코드를 발견했다.

    public static long solution(int k, int d)
    {
        long answer = 0;

        // 거리를 위해 제곱
        long dir_z = (long)Math.Pow(d, 2);

        for (int x = 0; x <= d; x += k)
        {
            for (int y = 0; y <= d; y += k)
            {
                // 각 거리마다 제곱을 구함
                long dir_x = (long)Math.Pow(x, 2);
                long dir_y = (long)Math.Pow(y, 2);

                // 최종 거리보다 작거나 같으면 그 때 증가
                if (dir_z >= dir_x + dir_y)
                {
                    ++answer;
                }
                else
                    break;
            }
        }

        return answer;
    }

 

 

 

다른 방법

x^2 + y^2 = z^2

이라는 방식을 x^2를 이항해서

y^2 = z^2 - x^2를 하게 되면 y의 최대값을 구할 수 있다.

 

이게 무슨 말인지 나도 이해는 안갔다

z^2가 총 거리이다.

여기서 원래 방식은 x^2 + y^2 = z^2 여서

x^2 + y^2 <= z^2보다 작으면 카운트가 증가하는 식으로 개발했다.

 

    public static long solution(int k, int d)
    {
        long answer = 0;

        // 거리를 위해 제곱
        long dir_z = (long)Math.Pow(d, 2);

        for (int x = 0; x <= d; x += k)
        {
            // 각 거리마다 제곱을 구함
            long dir_x = (long)Math.Pow(x, 2);

            int maxY = (int)Math.Sqrt(dir_z - dir_x);
            answer += (maxY / k) + 1;           // 1, 2, 3, 4, 5 가 나오는데 좌표는 원점 0을 포함하니 +1 count를 해줌
        }

        return answer;
    }

 

하지만 위 코드와 같이 계산하게 되면

 

즉 여기서 예를 들어 인자의 값이 k = 1, d = 5라는 값이 주어진다.

maxY는 x가 0일 때 maxY는 5(25)의 거리가 된다.

이 때 5(25)를 넘지 않는 것들을 카운트를 증가 시켜야 하는데,

5(z) - 0(x) = 5(maxY) 이렇게 계산을 하게 되면 x와 y가 z를 넘지 않는 maxY값이 나오고,

그 값을 k(증가량) 만큼 나누게 되면 maxY는 최대의 y가 나오게 되고 k가 x의 증가량을 맡고 있기에

(5(maxY) / 1(k)) 라는 값은 5가 나오게되고 찍을 수 있는 좌표는 총 5개

(0, 1), (0, 2), (0, 3), (0, 4), (0, 5) => 5개라는 값이 나온다.

좌표에서는 0도 포함이기에 +1을 해준다.

 

하나만 더 예를 들어보자.

x가 2까지 증가했다고 치면

25 - 4 = 21

 

그러면 이미 x가 증가한 값들은 최대 거리에서 빼고 난 나머지 y값을 계산한다.

 

이 21을 제곱근 하게 되면 4.5라는 거리가 나온다.

그러면 4.5를 넘지 말아야 하기 때문에

maxY값은 4가 되고,

(3, 0), (3, 1), (3, 2), (3, 3), (3, 4) 즉 5개의 값이 나올 수 있게 된다.

 

그렇게 다 더하게 되면 k = 1, d = 5라는 기준으로 문제가 나왔을 때 26이라는 개수가 나오게 된다.

 

 

어렵다 어려워.