멀쩡한 사각형

문제정의

---

1x1cm가 단위인 모눈종이에 그린 사각형의 가로, 세로길이가 주어진다. 여기에 꼭짓점을 잇는 대각선을 그었을 때, 선이 그이지 않은 1x1크기의 사각형의 개수를 구하는 문제이다. 이 문제는 직선의 방정식을 이용하여 문제를 풀었다.

문제풀이

---

전체 코드는 다음과 같다.

public class FineRectangle {

    //프로그래머스 문제풀이 level2 멀쩡한 사각형
    
    public static void main(String[] args)
    {
        int w = 8;
        int h = 12;

        long answer = 0;
        double a = h*(-1)/(double)w;
        int b = h;
        
        for(int i = 1; i < h; i++)
        {
            double x = (i-b)/a;
            answer += (long)x;
        }
        answer *= 2;

        System.out.print(answer);
    }
    
}

코드의 길이는 짧은 편이다. 일단 필자는 사각형을 2차원 좌표로 나타냈을 때, (0,h) 와 (w,0)을 지나는 직선으로 생각했다. 그러면 기울기 a와 y절편 b를 구할 수 있다. 그리고 y좌표가 1부터 h-1까지(왜냐하면 y좌표가 h이면 어차피 멀쩡한 사각형이 없다.) 각각의 x좌표를 구한다. 그렇다면 그 x좌표가 해당 높이의 대각선이 존재하는 위치이다. 그렇다면 계산한 x가 만약 6.12xxxxx 라면 멀쩡한 사각형은 해당 위치에서 12(6*2)개가 있을 수 있다. 필자는 직각삼각형에 존재하는 사각형을 모두 구한 뒤 이를 2배 했다. 필자와 비슷한 생각을 했다면 아마 프로그래머스에서 테스트 케이스 6번을 틀렸을 수도 있는데, 이는 부동소수점 오차가 영향을 줬기 때문이다. 필자도 x값을 구하는 과정에서 (i/a) - (b/a)를 썼는데 틀렸었다. 그래서 나누기를 최소화하는 방향으로 둘을 합치니 통과가 되었다. 실수형 연산을 할 땐 조심 또 조심하자.

최종적인 시간복잡도는 \(O(h)\)이다.

테스트

최대공약수를 통해서 이 문제를 푼 사람도 있었다. 도대체 그런 규칙은 어떻게 알아내는 지 신기하다. 패턴이 존재하는 것 같은 느낌은 받았지만, 필자는 그 규칙까지 찾아내지 못했다. 덕분에 유클리드 호제법도 익힐 수 있었다.