[PG] 멀쩡한 사각형 JAVA

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

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

문제 설명

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

제한사항

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

입출력 예

WHresult

8

12

80

입출력 예 설명

입출력 예 #1
가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.

 

 

 

 

 

 

풀이 .

 

->

 

 

예제를 바탕으로 조건을 찾아보고자 했다.

 

예제의 경우 w : h = 8 : 12 이고, 이걸 최대공약수 4로 나누면 2 : 3이 된다.

즉, 전체 map에서 선분이 지나가는 2 x 3 크기의 덩어리가 gcd개 존재하게 된다.

 

하지만 이 6칸의 사각형이 모두 선분에 걸치는 것은 아니다. 살릴 수 있는 부분도 존재한다. 이걸 계산하는 게 관건인 듯 하다.

 

라고 여기까지 생각했는데.. 자세히 생각해보니 굳이 w : h가 1이 아닌 최대공약수를 갖도록 맞아떨어지는 수가 주어진다는 보장이 없다. (이걸 굳이 여러 블럭으로 나누려고 할 필요가 없었다)

 

결국 다시 원점이다.

 

 

나누어 떨어지지 않는 경우에 대한 조건을 떠올리기 위해 w : h = 8 : 5 로 직접 그려보았다.

 

끝 열이 겹치는 형태로 2 x 1, 3 x 1의 3, 2개씩 반복되었다.

여기에서 규칙을 찾을 수 없을까?

(틀린 접근법이었다)

 

 

 

여기에서 더 나아가지 못하고 답을 확인했다.

 

우선 딱 나누어 떨어지지 않는 경우(gcd = 1인 경우)는 그냥 w x h사이즈의 블록이 gcd개 만큼 반복된다고 보면 된다.

즉,  (w / gcd) * (h / gcd) 사이즈가 gcd번 반복되는 일반식을 세우면 되는 것이다.

 

위에서 관건이라고 언급했던 이 gcd개의 덩어리에서 선분을 지나는 칸을 구하는 것도 일반식을 세울 수 있었다.

이 w/gcd = w', h/gcd = h' 으로 두어 이 덩어리의 사이즈가 w' x h' 라고 두었을 때, 선분이 지나는 칸의 개수는 w' + h' - 1개가 된다.

일반식이기 때문에 gcd가 몇이든 항상 동일하게 적용된다.

 

어떻게 이런 식이 도출되는가?

->

(w' x h')블록 안에서 선분은 항상 행, 열 중 하나에 대해서만 이동한다. 행과 열을 동시에 이동하는 경우, 즉, 대각선 방향으로 한 번에 이동하는 경우는 없다는 것이다. 

(전체를 놓고 봤을 때 대각선 방향으로 이동하는 경우가 있긴 하지만 이건 다음 (w' x h')블록으로 이동하는 것이다. 즉, 위의 빨간 글씨의 문장은 항상 성립하게 된다.)

 

그럼 결국 선분은 (w' x h')블록 안에서 행을 h'번, 열을 w'번 이동하게 된다. 하지만 블록의 맨 왼쪽위 칸은 첫번째 행과 첫번째 행을 동시에 표현하기 때문에 이 중복에 대한 처리로 -1을 해줘야 한다.

 

이렇게 w' + h' - 1 이란 식을 도출할 수 있게 된다.

 

결국 전체 맵에서 손상되지 않은 사각형의 개수는

(w * h) - (w' + h' - 1) * gcd 이라는 식을 통해 구할 수 있게 된다. (단, w' = w / gcd, h' = h / gcd)

 

 

 

 

 

 

class Solution {
    public int gcd(int a, int b) {
        if(b == 0) return a;
        else return gcd(b, a % b);
    }

    public long solution(int w, int h) {
        long answer = 0;
        int gcd = gcd(w, h);
        answer = ((long)w * (long)h) - (((long)w / gcd) + ((long)h / gcd) - 1) * gcd;
        return answer;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
    }
}

 

풀이를 찾아보며 BigInteger 클래스를 사용해서 gcd를 좀 더 편하게 구할 수 있는 방법이 있단 걸 알았다.

사실 원래 방식도 별 거 없어서 그게 그거이긴 하다.

(속도는 원래 방식이 아주 조금 더 빠른 듯 하다)

 

    import java.math.BigInteger;
    
    public int gcd(int a, int b) {
        BigInteger bi1 = BigInteger.valueOf(a);
        BigInteger bi2 = BigInteger.valueOf(b);
        BigInteger gcd = bi1.gcd(bi2);
        return gcd.intValue();
    }