[プログラマー]無傷の矩形
3131 ワード
問題の説明
長方形の紙があり、幅はWcm、長さはHcmです.
紙には水平方向と垂直方向に平行なグリッド線があり、すべてのグリッドは1 cm x 1 cmの大きさです.
1 cm(グリッドに沿って)× 1センチの正方形に切るつもりだったが、この紙を2つの対角線の頂点を結ぶ方向に切った人がいた.
したがって、現在の矩形紙は、同じ大きさの2つの直角三角形に分かれています.
新しい用紙が見つからないため、この用紙の横方向と縦方向は元の用紙と平行1 cmである× 1 cmに切って、使えるだけ使ってください.
横方向長さWと縦方向長さHが与えられた場合、使用可能な正方形の個数を求める解法関数を完了する.
せいげんじょうけん
W,H:1億以下の自然数
I/O例
に答える
function getGCD(w, h) {
const mod = w % h;
if (mod === 0) {
return h;
}
return getGCD(h, mod);
}
function solution(w, h) {
const gcd = getGCD(w, h);
return w * h - (w + h - gcd);
}
2級に上がってから初めて回答した質問ですが、すべての2級の質問がそうだったのかと驚きました.どうしたらいいか思い出せず、長い間悩んでいた.
線が点を通る部分を比率で計算することも考えられますが、なかなか解けません.
矩形の個数の公式を求めます
長方形の横+長方形の縦-(長方形の横、縦の最大公約数)
最大公約数
ユークリッド湖製法を利用する.
ユークリッドアークほう
const w = 8;
const h = 12;
1) 8(w) % 12(h) = 8(mod)
2) 12(이전 h) % 8(이전 mod) = 4(new mod)
3) 8 % 4(이전 mod) = 0
0이 나오면 4를 return 한다.
矩形の個数を求める公式を知らないのは全く解けない問題だが,コード自体は難しくない.長い間うろうろしていましたが、次はこれらの問題をうまく解決します.
Reference
この問題について([プログラマー]無傷の矩形), 我々は、より多くの情報をここで見つけました https://velog.io/@s_sangs/프로그래머스-멀쩡한-사각형テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol