116. 점 찍기

 

기본 틀 : 

 

using System;

public class Solution {
    public long solution(int k, int d) {
        long answer = 0;
        return answer;
    }
}

 

기본으로 제공되는 틀에서 반환형이 long인 것을 보고

 

'수행시간을 고려해서 코드를 작성해야 한다'

 

라는 생각을 했다.

 

해당 문제를 보면 d에 따라 x^2 + y^2 = d^2이라는 원 방정식을 얻을 수 있고

 

x^2 + y^2 <= d^2인 정수 좌표 (x, y)를 구하면 되는 문제였다.

 

그래서,

 

        long num = (long)Math.Pow(d, 2);

 

d의 제곱을 구하고

 

        long total = 0;
        for(int i = 0; i <= d; i+=k)
        {
            int sqrt = (int)Math.Sqrt(num - Math.Pow(i, 2));
            total += (sqrt / k) + 1;
        }

 

x, y 중 하나의 축을 잡고 0 ~ d 까지 k를 증가시키면서 

 

// sqrt  = Sqrt(d^2 - x^2)

 

 

(d^2 - x^2)의 제곱근을 구하면 하나의 점에 따른 다른 점에 찍을 수 있는 모든 정수 점의 개수를 구할 수 있게 된다.

 

// (sqrt / k)

 

이렇게 구해진 점을 k로 나누게 되면 k 증가에 따른 정수 점의 개수를 구할 수 있게 되고 해당 개수에 

 

total += (sqrt / k) + 1;

 

+1을 해서 y와 x가 동일한 지점을 추가해주면 됐다.

 

전체 코드 : 

using System;
using System.Linq;
using static System.Math;

public class Solution {
    public long solution(int k, int d) 
    {
        long num = (long)Math.Pow(d, 2);
        
        long total = 0;
        for(int i = 0; i <= d; i+=k)
        {
            int sqrt = (int)Math.Sqrt(num - Math.Pow(i, 2));
            // (d^2 - x^2) 하나의 점에 따른 다른 점에 모든 정수 개수
            
            // k 증가에 따른 정수 점의 개수
            total += (sqrt / k) + 1; // +1은 y와 x가 동일한 지점
        }
        
        return total;
    }
}