[Programmers] 2019 summer/winter : 멀쩡한 사각형 #62048

문제 링크

멀쩡한 사각형

문제 조건

• 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다.
• 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓아서 잘라지지 않은 부분만 사용하기로 했습니다.
• 이 때, 사용할 수 있는 정사각형의 개수를 구하시오.

변수 설명

• W : 가로의 길이 (매개변수)
• H : 세로의 길이 (매개변수)
• mul : 모든 정사각형의 개수( W * H ) : long 타입
• line : 사용할 수 없는 정사각형의 개수

코드 설명

• 문제를 처음 접했을 때, 어떻게 풀어야 할지 감이 안잡혀서 무작정 W가 7까지 그림을 그려보고 규칙을 찾아보았습니다.
  

  

• 일단 W * H에서 얼마나 빠지는지 생각해보았습니다.
• 첫 번째로, 주의깊게 봤던 부분은 W와 H의 값이 같을 때, 사용할 수 있는 W * H - W 개입니다.
• 두 번째로, W=7일 때,최대공약수가 1이므로 쉽게 알아챌 수 있었습니다.

  문제 해답

class Solution {
    public long solution(int w,int h) {
        if(w == 1 || h == 1) return 0;
        long mul = (long)w * (long)h;
        long line = w + h - gcd(w,h);

        return mul - line;
    }
    int gcd(int w, int h) {
        return w % h == 0 ? h : gcd(h, w % h); 
    }
}