[Programmers]멀쩡한 사각형_자바

https://programmers.co.kr/learn/courses/30/lessons/62048?language=java 

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

해당 문제는 자료구조 지식을 요구한다기 보다는 문제를 잘읽고 규칙을 찾아내는 수학문제와 더 가깝다고 볼수 있을것 같습니다.

문제를 보자마자 무슨 규칙이 있겠다 생각이 들었는데요 위의 그림을 보면 같은 모양의 멀쩡하지 않은 사각형모양이 있는걸 볼 수 있습니다.

또 우연치 않게 8과 12의 최대공약수가 4인데요.

아 먼저 최대 공약수를 구해서 w와 h를 최대공약수로 나눈 다음 그 수에서 멀쩡하지 않은 사각형의 갯수를 구해서 최대공약수만큼 다시 곱해주면 사용할수 없는 사각형의 갯수가 나오겠구나 라는 생각이 들었습니다.

class Solution {
    public long solution(long w, long h) {
        long answer = w * h;
        
        long cnt = 0;
        long tmp = 0;
        
        for(long i = 1; i <= w; i++){
            if(w % i == 0 && h % i == 0){
                cnt = i;
            }
        }
        
        w /= cnt;
        h /= cnt;
        
        if(w == h){
            tmp = w;
        }else{
            tmp = w + h - 1;
        }
        
        answer -= cnt * tmp;
        
        return answer;
    }
}

코드만 보면 정말 간단합니다.

맨처음에는 answer에 w와 h를 곱한 값을 넣어주었습니다.

 

cnt는 최대공약소를 구하기 위함이고 tmp는 최대공약수로 나눈 w와 h에서 사용할수 없는 사각형을 구하기 위한 변수입니다.

w와 h가 같은숫자일떄는 사용할수 없는 사각형을 구하는것이 정말 간단해요!

2 * 2일경우 2개의 사각형이 멀쩡하지 않고 3*3일때는 3개의 사각형이 멀쩡하지 않더라구요.

아 즉 정사각형 일때는 길이만큼 사용할수 없구나 라는 생각을 하게 되었습니다.

하지만 그 외의 경우인데요.

이것 저것 다 계산해 봤을때 우연치 않게 w + h - 1개만큼 사용할수 없는 사격형이 된다는 규칙을 발견하게 되었습니다.

 

이런 규칙을 적용하여 코드로 옮긴 결과 테스트케이스가 통과하였습니다!