[Programmers] 멀쩡한 사각형 (Java)

문제링크

문제 설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.
가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.

제한사항

• W, H : 1억 이하의 자연수

입출력 예

W	H	result
8	12	80

문제풀이

총 두 가지 풀이법이 있었다. 두 풀이 모두 결국, 대각선이 지나는 사각형의 개수를 구하는 풀이이다.

 

첫 번째 풀이방식은 수식을 이용하였다. 대각선은 항상 각 사각형들의 왼쪽 위쪽 꼭지점 이거나 왼쪽 변을 지나게 된다. 두 경우에 따라, 제거되는 사각형의 개수가 정해지게된다. 아래 그림의 직사각형을 왼쪽 하단을 원점으로 하는 좌표축이라 생각해본다면, 대각선을 직선방정식으로 표현할 수 있게된다. 구한 직선방정식에 x 값 (정수)를 넣게 되면, y값이 나올텐데, 연속한 두 y 값들 (즉, (x, y1), (x + 1, y2))을 구하고, y1, y2와 x, x+1 사이의 사각형 개수 간의 관계를 알아내면 문제가 해결되었다. 여러 경우를 확인해본 결과, y1 값이 자연수냐 아니냐에 따라 사각형 개수가 정해졌다. (y2는 관계가 없었다.) 두 경우 모두 우선 y1, y2를 내림해주고, 자연수가 아닐 경우에만 1을 추가로 더해주었더니, x와 x+1 사이의 사각형 개수가 나왔다.

가로 x, 세로 y (출처: Programmers)

 

두 번째 풀이방식은 공식을 이용하는 것이였다. 몰랐던 사실인데, 문제를 풀고 난 뒤 다른사람의 풀이를 확인해보니, 대부분이 최대공약수를 이용해 문제를 풀었다. 대각선이 지나는 사각형을 구하는 공식이 있었던 모양이다. 확실히 이 방식이 풀이가 더 간단하고, 시간복잡도 또한  더 작았다. 첫 번째 풀이방식은 O(w) 이지만, 이 풀이방식의 경우, 최대공약수를 유클리드 호재법으로 구하게 된다면, 시간복잡도가 O(logN)이 되기 때문이다.

 

코드

Java

public class FineSquare {

	// 첫 번째 풀이방식
    public long solution(int w, int h) {
        long answer = 0;

        for (long x = 0; x < w; x++) {
            answer += countSq(w, h, x, x + 1);
        }

        return ((long) w * h) - answer;
    }

    private long countSq(long w, long h, long x1, long x2) {
        double y1 = eqY(w, h, x1);
        double y2 = eqY(w, h, x2);

        return (long) (Math.floor(y1) - Math.floor(y2)) + (y1 % 1 == 0 ? 0 : 1);
    }

    private double eqY(long w, long h, long x) {
        return -1 * ((double) x * h / w) + h;
    }
    
	// ===========================================================================
    //
	// 두 번째 풀이방식
    public long solution2(int w, int h) {
        return (long) w * h - (w + h - gcd(w, h));
    }

    private long gcd(long w, long h) {
        return w == 0 ? h : gcd(h % w, w);
    }
}