Informatica Online Judge

  정사각형 채우기 [1079 / 0437]

Time Limit(Test case) : 100(ms)
Number of users who solved : 539   Total Tried : 765


The Champion of this Problem (C++) : gs16051 - ms / 185byte
My Best Submission (C++) : N/A

[JeongHJ]

Background

n × m 크기의 격자를 모노미노와 도미노로 채우는 놀이를 하던 병찬이가 재미가 없던지 정사각형을 이용하여 격자를 채우는 방법에 골돌하고 있다가 다음과 같은 방법으로 격자를 채우는 놀이로 변경하였다.

(1) 정사각형의 크기는 제한이 없고 정사각형은 무한히 많다.
(2) 단, n, m 중에서 작은 값을 한 변으로 하는 정사각형을 반드시 한 번 사용한다.

위 방법으로 큰 사각형을 채울 때 사용하는 정사각형의 갯수를 출력하는 프로그램을 작성하시오.

(반복문 불가, 반드시 재귀함수로 작성하시오.)

Input

첫 줄에 n, m이 입력된다.(1<=n<=2^31)

Output

격자를 채우기 위해 필요한 정사각형의 최소의 수를 출력한다.

IO Example

입력1
3 5

출력1
4


입력2
9 3

출력2
3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]