プログラマレベル2-3
7137 ワード
正方形
問題の説明
長方形の紙があり、幅は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を返します.
この問題は知っていることが大きいほど、同じパターンが繰り返されて解決できないので、他人のブログを参考にしました.
1)繰り返しは正しいが、繰り返しのルールがある
図中の横8は縦12で、4つの繰り返しパターンがあります.これは、横方向の最大公約数に従って繰り返されるルールです.
2)この規則に従って小さく切る
横4縦6の場合、同じパターンが繰り返され、最大公約数は2です.
消去された矩形の個数は横方向+縦方向−最大公約数であることが分かった.
3)だから答え=w*h-(w+h-maxヤク).
問題の説明
長方形の紙があり、幅は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を返します.
この問題は知っていることが大きいほど、同じパターンが繰り返されて解決できないので、他人のブログを参考にしました.
1)繰り返しは正しいが、繰り返しのルールがある
図中の横8は縦12で、4つの繰り返しパターンがあります.これは、横方向の最大公約数に従って繰り返されるルールです.
2)この規則に従って小さく切る
横4縦6の場合、同じパターンが繰り返され、最大公約数は2です.
消去された矩形の個数は横方向+縦方向−最大公約数であることが分かった.
3)だから答え=w*h-(w+h-maxヤク).
import java.util.*;
class Solution {
public long solution(int w, int h) {
int min = (w<h) ? w : h ;
int max = (w>h) ? w : h ;
int max_yak = 0;
ArrayList<Integer> yak = new ArrayList<Integer>();
for(int i=1; i<=min ;i++){
if( min % i==0) yak.add(i);
}
System.out.println(yak);
for(int i=0 ;i<yak.size(); i++){
if(max%yak.get(i)==0) {
max_yak =yak.get(i);
}
}
System.out.println("max = " +max);
long answer = (long)w*(long)h -(long)(w+h-max_yak);
return answer;
}
}
Reference
この問題について(プログラマレベル2-3), 我々は、より多くの情報をここで見つけました https://velog.io/@park517/프로그래머스-level-2-3テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol