[プログラマー]通常の長方形(Java)

🔗 質問リンク

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

📌解析トラブルシューティング方法(モード)

これらの問題を解決するためには,結果をチェックし,確認し,問題のパターンを見つけるために直接数を描く必要がある場合が多い.
まず、最も基本的な1:1の割合の矩形で、対角線を接続したときにカットされた矩形の個数をチェックします.

結果は,n:nスケールの矩形がn個の矩形が剪断されることを決定できることを示した.

1:2スケールの矩形については,4 n個の矩形が切り取られているのが見られ,それ以外にも複数のスケールの矩形を描いて切り取ってみた.


いくつかの図を描き,パターンを解析した結果,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);
    }
}

📝 n/a.結論

問題の解決策を見つけてコードを書くのに20分もかかりません.
ただし、テストキャビネット12−17のデータ量が大きいため、intではなくlongタイプに完全に変換するには長い時間がかかる.
問題を解くときは、入力値の制限を確認してからデータ型を特定する習慣を身につけましょう.