[프로그래머스] 멀쩡한 사각형 (Java)

🔗 문제 링크

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

📌문제 해결법(패턴) 분석

이러한 문제를 풀기 위해서는 여러 경우의 수를 직접 그려서 체크해보고 결과를 확인하며 문제의 패턴을 찾아내야한다.

나는 먼저 가장 기본적인 1:1 비율의 사각형에서 대각선을 연결했을 때 잘려나가는 사각형의 개수를 체크해보았다.

그 결과 n:n의 비율의 사각형은 n개의 사각형이 잘리는 것을 확인할 수 있었다.

1:2비율의 사각형의 경우는 4n개의 사각형이 잘리는 것을 확인할 수 있었으며 그 외에도 여러 비율의 사각형을 그리고 잘라보았다.

여러 그림을 그리고 패턴을 분석해본 결과 a:b(a,b는 서로소)의 비율의 사각형을 대각선으로 연결하였을 경우 a+b-1개의 사각형이 잘려나가는 패턴을 찾을 수 있었다.

이렇게 찾은 패턴을 이용하여 코드를 작성해보았다.

👨🏻‍💻 작성한 코드

class Solution {
    public long solution(int w, int h) {
        long answer;
        
        int whGcd = gcd(w, h);
        long wRate = (long)w/whGcd;
        long hRate = (long)h/whGcd;

        answer = (long)w*(long)h - (wRate+hRate-1) * whGcd;
        
        return answer;
    }
    
    public int gcd(int a, int b){
        if(a%b == 0) return b;
        else return gcd(b, a%b);
    }
}

📝 결론

문제의 해결법을 찾고 코드를 작성하기까지는 20분도 안되는 시간이 걸렸던 것 같다.
하지만 테스트 케이스 12~17번의 데이터 크기가 큰 이유때문에 int로 표현할 수 있는 범위를 넘어서 연산을 완전하게 long타입으로 변환시키는데 오랜 시간이 걸렸던 것 같다.

문제를 풀 때 input값에 대한 제한 사항을 확인 후 데이터 타입을 정해주는 습관을 키워야겠다.