실력키우기 타일교체(C++)

2810 : 타일교체

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 462 회    시도횟수: 1021 회   

화장실 바닥을 새로운 타일로 교체하려고 한다. 타일은 모두 정사각형 모양으로 한 변의 길이는 정수로 표시되어 있다.

타일의 크기를 여러 가지로 하면 보기가 싫기 때문에 모두 같은 크기의 타일을 사용하려고 한다.

타일의 개수가 많아지면 비용이 많이 들기 때문에 타일의 개수는 가능하면 최소한으로 사용하려고 한다.

화장실의 가로의 크기와 세로의 크기가 주어질 때 필요한 최소 타일의 개수를 구하는 프로그램을 작성하라.

 

화장실 가로의 길이와 세로의 길이가 차례대로 입력된다.
1 <= 가로, 세로 <=1,000,000

필요한 최소 타일의 개수를 출력한다.

[Copy] 24 30

[Copy] 20

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

/**************************************************************     Problem: 2810     User: a132034     Language: C++     Result: Success     Time:1 ms     Memory:1740 kb ****************************************************************/     #include    <iostream> using namespace std;     int getGCD(int a, int b);   int main() {     int h, w;     cin >> w >> h;       int gcd = 0;     if (w > h)         gcd = getGCD(w, h);     else         gcd = getGCD(h, w);       h /= gcd;     w /= gcd;       cout << h*w;   }   int getGCD(int a, int b) {     if (a%b == 0) return b;     return getGCD(b, a%b); }

도움말

※ 한 변의 길이가 6인 타일로 채우면 가장 적은 개수가 된다.

도움말을 확인하면 상당히 쉬운 문제, 확인하지 않았더라도 그림을 그려본다면 어느정도 쉽게 풀 만한 문제였다. 

정사각형의 타일이 들어가기 위해 우선 가로로도 세로로도 타일이 잘리면 안된다 -> 타일의 한 변의 x배 ,y배를 하면 가로, 세로 길이가 되어야 한다는 것을 의미한다. 

결국 가로와 세로의 공약수를 이용하면 타일을 자르지 않고 넣을 수 있다. 이중 가장 적게 사용한다고 하였으니, 최대공약수를 사용. 

한 변의 길이를 구했으면, 몇 개의 타일이 들어갈 지 구해주면 완료.