[프로그래머스,자바] Level2:멀쩡한 사각형

문제분석

문제를 이해하기는 매우쉽다. 대각선으로 선을 그은뒤,  잘라진 사각형을 제외한다.

 

그런데, 잘라진 사각형을 어떻게 계산해야하는지 정말 막막하다.

무슨 특수한규칙이 있을텐데, 제로베이스로 그 규칙을 떠올리긴 매우 힘들다.

 

작성자는, 규칙을 발견하지못해서 참고자료를 검색하고 보면서 풀었다.

 

8X12 사각형을 잘려나간 사각형의 모양을 자세히보면, 같은모양이 4번 반복된다.

 

이 반복되는 횟수가, 가로와 세로의 최소공배수의 횟수만큼 반복한다.

(최소공배수 구하는 로직은 유클리드 호제법을 참고하세요!)

 

반복되는 모양의 갯수는 (가로/최소공배수)+(세로/최소공배수)-1 만큼의 갯수다.

 

전체 갯수- (최소공배수)*((가로/최소공배수)+(세로/최소공배수)-1)가 답이다.

문제풀이

 

class Solution {
    public long solution(long w, long h) {
        long answer = 1;
        long a =gcd(w,h);
        return answer=w*h-a*((w/a)+(h/a)-1);
    }
    public long gcd (long w,long h){
        while(h!=0){
            long r=w%h;
            w=h;
            h=r;
        }
        return w;
    }
}