[Java] 선을 넘나드는 사각형

1. 문제

정사각형이 빼곡하게 그려진 종이가 있다. 이 종이는 가로로 N 개의 정사각형이 배치되어 있고, 세로로 M 개의 정사각형이 배치되어 있다.

이 종이의 좌측 상단점부터 우측 하단점까지 직선을 긋는다.

 

예를 들어 N=4, M=9 인 경우 아래 예시사진과 같이 직선이 그어진다.

예시 사진

 

이 직선에 의해 내부에 선이 그어진 사각형은 총 12개이다.

주어진 입력 N, M 에 대해서 위와 같이 내부에 선이 그려지는 사각형의 수를 출력하시오.

 

 

2. 입력설명

• 0 < N <= 1000
• 0 < M <= 1000

 

3. 매개변수 형식

N = 4, M = 9

 

 

4. 반환값 형식

12

 

5. 예시 입출력 설명

본문 예시와 같이 총 12 개의 사각형 내부에 선이 그려진다.

 

 

6. 내가 생각해 본 방법

직선을 그래프로 생각했을 때 그래프는 y = -M / N * x + M 이다. 이때 x 는 정수의 값을 가진다.

x의 값에 따라 나온 y의 값에서 내림한 값의 모든 합에서 (x2)를 하여 N*M 에서 빼면 정답이다.

 

class Solution {
    public int solution(int N, int M) {
        int count = 0;
        
        for (int i = 1; i < N; i++) {
            double y = ((double) (-M) / N ) * i + M;
            count += (int) (M - Math.ceil(y));
        }
        return (N*M) - (2 * count);
    }
}

 

 

7. 다른 풀이 방법

기본적으로 직선이 아래나 우측으로 이동하기 때문에, N+M 개의 정사각형을 지난다.

하지만, 정확히 모서리를 지나는 경우가 있기 때문에 숫자가 몇 번 덜 증가한다.

그 횟수는 총 N과 M의 gcd(최대공약수) 가 된다.

 

class Solution {
    public int solution(int N, int M) {
        // 일반적으로 직선이 지나는 정사각형의 개수 = N + M
        // 정확히 모서리가 맞아서 직선을 지나지 않는 경우의 수 = N과 M의 최대공약수
        return N + M - gcd(N, M);
    }

    // 유클리드 호제법을 이용한 최대공약수
    int gcd(int x, int y) {
        if (y == 0) {
            return x;
        }
        return gcd(y, x % y);
    }
}