[プログラマー]無傷の矩形


正方形
問題の説明
長方形の紙があり、幅はWcm、長さはHcmです.紙には水平方向と垂直方向に平行なグリッド線があり、すべてのグリッドは1 cm x 1 cmの大きさです.1 cm(グリッドに沿って)× 1センチの正方形に切るつもりだったが、この紙を2つの対角線の頂点を結ぶ方向に切った人がいた.したがって、現在の矩形紙は、同じ大きさの2つの直角三角形に分かれています.新しい用紙が見つからないため、この用紙の横方向と縦方向は元の用紙と平行1 cmである× 1 cmに切って、使えるだけ使ってください.
横方向長さWと縦方向長さHが与えられた場合、使用可能な正方形の個数を求める解法関数を完了する.
せいげんじょうけん
W,H:1億以下の自然数
I/O例
W H result
8 12 80
I/O例説明
I/O例#1
幅8、奥行き12の長方形を対角線方向に切り取ると、合計16個の正方形が使用できません.元の長方形は96個の正方形を作成することができ、96~16=80を返します.

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

📋 プール(タイムアウト)



対角線を座標平面の傾斜として表示します.yを1からheightに接するx座標を上げ、その後のスペースを増やします.(widx-x)対角線に準じて左右対称で半分だけ求め,求めた値の2倍を出力する.少し時間を減らすためにwidthとheightでheightとしてより短い長さを指定しましたが、タイムアウトが発生しました.widthとheightの長さの差は多くなく,その大きさは非常に大きいようだ.
import math

def solution(width, height):
    half_count = 0
    
    if height > width:
        width, height = height, width
    
    a = height / width  # 기울기
    
    for y in range(1, height):
        x = math.ceil(y / a)
        half_count += width - x
    
    return half_count * 2

📋 他人を解く


https://leedakyeong.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EB%A9%80%EC%A9%A1%ED%95%9C-%EC%82%AC%EA%B0%81%ED%98%95-in-python
widthとheightを用いると,対角線を通過する周囲パターンが同じになり,最大公約数の式が繰り返される.詳細はブログを参照してください.
import math

def solution(w,h):
    return w * h - (w + h - math.gcd(w, h))
対角線の周りに同じパターンがあるのは知っていますが、どのような基準で繰り返されているのか分かりません.また、スーパーが発生した場合、彼は別の角度から見るのではなく、コードの問題を見つけることを急いでいます.ほとんどのタイムアウトは、メソッドエラーではなく、まったく異なる方法で解決する必要がある問題であることに注意してください.
20211026
以前のブログで他の質問を探していましたが、以前は解読に失敗したコードを発見しました.その時に比べてコード長も減少し,テスト例も成功した.うれしく思う😊