C# 점 찍기 - 완전탐색 / 프로그래머스 [Lv.2]

출처: 프로그래머스 코딩 테스트 연습
https://school.programmers.co.kr/learn/courses/30/lessons/140107

 

 

1차 시도

public long solution(int k, int d) 
{
    long answer = 0;
    long dd = d * d;
    long kk = k * k;

    for(long a = 0; a * k <= d; ++a)
    {
        long xx = a * k * a * k;
        long y = (long)Math.Sqrt((dd - xx) / kk);
        answer += (y + 1); // 0이 포함되야함
    }
    return answer;
}

뭐지 너무 쉬운데 하고 적었다가 실패. 보통은 이러면 타입캐스팅 문제다.

 

피타고라스로 y의 해를 구해서 풀었는데,

완전탐색으로 풀려면 거리는 유니티에서 벡터의 magnitude로 계산하듯 제곱상태에서 비교하는게 최적화하기 좋다.

 

나의 풀이

public long solution(int k, int d) 
{
    long answer = 0;
    long dd = (long)d * d;
    long kk = (long)k * k;

    for(long x = 0; x <= d; x += k)
    {
        long xx = (long)x * x;
        long y = (long)Math.Sqrt((dd - xx) / kk);
        answer += (y + 1); // 0이 포함되야함
    }
    return answer;
}

1.

위에서는 a를 기준으로 a * k 해서 x를 구했는데,

등차수열이니 for문의 반복변수로 사용해서 x += k 해줬다.

이건 코드 최적화의 문제니 안해도 상관없음.

 

2. int 변수 d 를 제곱할 때 타입 캐스팅 오류.

곱할때 두 피연산자가 int기 때문에 오버플로우가 나버린 다음에 long 컨테이너에 캐스팅하면서 넣게된다.

한쪽을 long으로 미리 캐스팅하고 계산해야한다.

long dd = d * d; // 틀림! 오버플로우
long dd = (long)d * d; // 정답! 정상작동

 

실수할것을 생각해봐도 레벨 2로는 안보이는 문제.