プログラマーSummer/Winter Coding(2019)-完全な長方形
問題の説明
長方形の紙があり、幅はWcm、長さはHcmです.紙には水平方向と垂直方向に平行なグリッド線があり、すべてのグリッドは1 cm x 1 cmの大きさです.1 cm(グリッドに沿って)× 1センチの正方形に切るつもりだったが、この紙を2つの対角線の頂点を結ぶ方向に切った人がいた.したがって、現在の矩形紙は、同じ大きさの2つの直角三角形に分かれています.新しい用紙が見つからないため、この用紙の横方向と縦方向は元の用紙と平行1 cmである× 1 cmに切って、使えるだけ使ってください.
横方向長さWと縦方向長さHが与えられた場合、使用可能な正方形の個数を求める解法関数を完了する.
せいげんじょうけん
I/O例
WHresult81280
I/O例説明
幅8、奥行き12の長方形を対角線方向に切り取ると、合計16個の正方形が使用できません.元の長方形は96個の正方形を作成することができ、96~16=80を返します.
に答える
規則を探すのは簡単だが,見つからないのは難しい.
長方形を半分にカットしたときに無効になった長方形の数は、次のとおりです.
8 X 12 -> 16
4 X 5 -> 8
3 X 4 -> 6
2 X 4 -> 4
5 X 8 -> 12
4 X 4 -> 4
絵を描いている間にルールを探すのに苦労しましたが、失敗しました...
しかし、後で発見するのは簡単です.
ヒントは最大公約数です.
w+hで最大承諾数を減算すると、使用できない矩形数が現れます.def solution(w, h):
answer = w*h - (w+h-gcd(w,h))
return answer
def gcd(x, y):
r = x % y
if r == 0:
return y
return gcd(y, r)
ああ...ちょっと濡れ衣を着せる
Reference
この問題について(プログラマーSummer/Winter Coding(2019)-完全な長方形), 我々は、より多くの情報をここで見つけました
https://velog.io/@whanhee97/프로그래머스-SummerWinter-Coding2019-멀쩡한-사각형
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
規則を探すのは簡単だが,見つからないのは難しい.
長方形を半分にカットしたときに無効になった長方形の数は、次のとおりです.
8 X 12 -> 16
4 X 5 -> 8
3 X 4 -> 6
2 X 4 -> 4
5 X 8 -> 12
4 X 4 -> 4
絵を描いている間にルールを探すのに苦労しましたが、失敗しました...
しかし、後で発見するのは簡単です.
ヒントは最大公約数です.
w+hで最大承諾数を減算すると、使用できない矩形数が現れます.
def solution(w, h):
answer = w*h - (w+h-gcd(w,h))
return answer
def gcd(x, y):
r = x % y
if r == 0:
return y
return gcd(y, r)
ああ...ちょっと濡れ衣を着せるReference
この問題について(プログラマーSummer/Winter Coding(2019)-完全な長方形), 我々は、より多くの情報をここで見つけました https://velog.io/@whanhee97/프로그래머스-SummerWinter-Coding2019-멀쩡한-사각형テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol