[Programmers] 멀쩡한 사각형

[Level 2] 멀쩡한 사각형

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

• 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm * 1cm 크기 입니다.
• 누군가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라놓았습니다.
• 가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해주세요.

 

 

Solution

• 아이디어를 생각하기 어렵다 ㅠ-ㅠ,,
• 예시를 기준으로 12*8 크기의 직사각형 종이가 있을 때, 사용할 수 없는 정사각형의 패턴을 보면 2*3 크기의 직사각형 내에서 테트리스 모양의 4개의 정사각형은 사용할 수 없음을 알 수 있다.
• 여기서  다음과 같은 식을 도출 할 수 있고, 2(W) + 3(H) - 1 = 4
• 12*8 직사각형에서 이러한 패턴을 가진 2*3 직사각형의 개수는 총 4개이다. 4 * (2 + 3 - 1 ) =16
• 4개의 직사각형 개수는 12와 8의 최대 공약수를 의미한다. 
• 따라서 사용할 수 없는 정사각형의 개수는 W + H - (W, H)의 최대공약수라는 식을 도출 할 수 있다.

 

 

 

소스코드

 

class Solution {
    public long solution(int w, int h) {
       long lw = (long)w;
        long lh = (long)h;
        long answer = lw*lh;
       
        answer -= (lw + lh - gcd(lw,lh));
        return answer;
    }
    
    public static long gcd(long w, long h){
        if(h == 0){
            return w;
        }else{
            return gcd(h, w%h);
        }
    }
}