프로그래머스 - 점 찍기(Java)

구현 문제입니다.

 

문제를 요약하면,

거리가 d 이하인 x, y좌표 정수의 개수를 구하는 문제입니다.

단, 각 좌표는 k 배수입니다.

익숙한 그림 아닌가요?

네, 피타고라스 정리를 이용하면 아주 쉽게 문제를 해결할 수 있습니다.

 

각 좌표는 k의 배수입니다.

즉, x좌표를 0~d까지 k배수만큼 증가를 시키면,

각 x마다 가능한 y를 구해야 하는 방정식이 주어지게 됩니다.

이 방정식이 바로 피타고라스 정리입니다.

거리 d는 고정된 값입니다.

피타고라스 정리를 통해 알게되는 y는 해당 x좌표에서의 최대 y좌표의 거리입니다.

y역시 k의 배수이기 때문에, 최대 y좌표의 거리에서 k만큼 나누게 된다면

거리 d이하의 좌표 개수를 알 수 있게 됩니다.

 

 

[구현 코드]

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

        // x 좌표를 k 배수만큼 증가
        for(int i=0; i<=d; i+=k){
            int yMaxDistance = yPossibleDistance(i, d);
            answer += yPossibleCount(yMaxDistance, k);
        }
        return answer;
    }

    /*
     * 피타고라스 정리
     * y² = d² - x²
     * */
    private static int yPossibleDistance(int x, int d){
        long xx = (long) Math.pow(x, 2);
        long dd = (long) Math.pow(d, 2);

        int result = (int)(Math.sqrt(dd-xx));
        return result;
    }

    // '0'~'y 최대치 정수'에서, k 배수의 숫자가 몇 개 있는지 확인
    private static int yPossibleCount(int possible, int k){
        int y = (possible/k);
        return y+1;
    }
}