[Level 2] 멀쩡한 사각형

해당 문제를 푸는데 좀 많은 시간이 소요되었다. 먼저 문제를 살펴보면 아래와 같다.

 

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

즉, 8 x 12에서 흰색칸을 모두 지운 80이라는 값이 반환이 되어야 한다.

먼저 아래처럼 패턴을 나누었다. 패턴을 나누는 기준은 연속되지 않은 흰색 칸을 기준으로 했다.

그럼 패턴이 총 4개가 나오게 된다. 패턴의 길이는 가로 2, 세로 3인데, 이 값들은 가로와 세로를 각각 4로 나눈값이 된다. 하나 더 예시로 작성해 보았다. 

사용 못하는 칸이 모두 연속되어 있으므로 패턴이 1개이고 패턴의 길이는 가로 4, 세로 3이 된다. 패턴의 길이와 총 길이가 같으므로 패턴의 가로와 세로는 각각 1로 나눈 값과 동일하다. 이렇게 5x3, 6x4 등등의 길이의 종이를 위와 같은 방법으로 구해보았다. 

 

그 결과, 각 패턴의 길이는 종이의 가로, 세로값을 최대공약수로 나눈 값이 되며 패턴의 개수는 최대공약수의 값과 동일하다는 결론이 나왔다. 다시 위에 문제로 돌아가 패턴을 살펴보면,

패턴의 가로는 2, 세로는 3이 되는데 여기서 사용할 수 없는 칸은 총 4칸이다. 이 값 또한 가로와 세로를 더한 후 -1을 해주면 된다. 그 이유는 아래와 같다.

그림에서 볼 수 있듯이 3번을 위로, 4번을 왼쪽으로 붙이게 되면 패턴의 가로 + 세로 - 1 이 되기 때문에 사용하지 못하는 개수는 총 4개이다. 위에서 4x3 패턴의 예시도 동일하게 아래 그림처럼 가능하다. 

3, 5번을 왼쪽으로 붙이고 4, 6번을 위로 붙이게 되면 4 + 3 - 1 만큼의 개수를 사용하지 못하게 된다. 

위 내용을 코드로 작성하여 제출했다.

https://github.com/banjjak2/Programmers/blob/main/Level2/%EB%A9%80%EC%A9%A1%ED%95%9C_%EC%82%AC%EA%B0%81%ED%98%95.java

class Solution {
    public long solution(int w, int h) {
        long answer = 0;
        long totalCount = (long)w * h;
        // 패턴 총 개수
        int patternCount = gcd(w, h);

        // 1패턴당 가로 개수
        int widthPerPattern = w / patternCount;
        // 1패턴당 세로 개수
        int heightPerPattern = h / patternCount;
        // 1패턴당 못쓰는 개수
        int unusedCountPerPattern = widthPerPattern + heightPerPattern - 1;

        // 총개수 - (1패턴당 못쓰는 개수 * 패턴 총 개수);
        answer = totalCount - (unusedCountPerPattern * patternCount);
        return answer;
    }

    // 최대공약수 구하기
    public int gcd(int n, int m){
        // 나머지가 0이면
        if (m == 0){
            // 나눈값 반환
            return n;
        }

        // 나눈 수, 나머지 값
        return gcd(m, n % m);
    }
}