[프로그래머스] 멀쩡한 사각형 Java

programmers.co.kr/learn/courses/30/lessons/62048

코딩테스트 연습 - 멀쩡한 사각형

 

문제 요약

한 칸이 1 x 1로 구성된 w x h 칸의 종이가 있다. 이 종이를 대각선 꼭짓점 2개를 잇는 방향으로 잘랐을 때 손상되지 않은 1x1 크기의 칸의 개수를 구하시오.

문제 풀이

우선 w와 h의 값이 최대 1억이기 때문에 최대공약수로 나누어서 해결한 다음에 최대공약수(GCD)를 곱해주는 방식을 사용해야 편하다.  최대공약수를 구하는 함수를 따로 만들었는데 유클리드 호제법을 이용해서 구현하였다. 그 후 종이를 잘랐을 때 사용할 수 없는 칸을 구하는 규칙을 찾아보았고 가로 + 세로 - 1 만큼 사용할 수 없다는 규칙을 찾아냈다. 따라서 (w/GCD + h/GCD - 1) * GCD라는 공식으로 손상된 칸의 개수를 구할 수 있고 w * h에서 손상된 칸을 빼면 사용 가능한 칸이 나온다는 것을 알 수 있다.

 

주의해야 할 점은 w * h의 최대값이 1억 * 1억 까지 나올 수 있기 때문에 long으로 캐스팅 후 계산해줘야 한다는 점이다. 

 

나의 코드

class 멀쩡한_사각형 {
    public long solution(int w, int h) {
        long GCD = getGCD(Math.max(w, h), Math.min(w, h));

        return (long)w * (long)h - (w + h - GCD);
    }

    /* 유클리드 호제법을 이용해 최대공약수 구하는 함수 */
    public long getGCD(int x, int y) {
        while (x % y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return y;
    }
}