시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 824 | 114 | 71 | 19.189% |
상근이는 상근날드에서 N행 M열 크기의 초콜릿을 사은품으로 받았다. 상근이는 이기적으로 살면 안 된다는 부모님의 가르침을 마음속에 새기고 있었다. 따라서, 그는 친구들과 초콜릿을 나누어 먹으려고 한다.
문제를 열심히 찾아보다보면 분명히 상근이가 정사각형을 좋아한다는 문제를 찾을 수 있을 것이다. 따라서, 상근이는 초콜릿을 쪼개서 모두 정사각형 모양으로 만들려고 한다. 상근이는 초콜릿을 베스트 프랜드에게만 나누어 주려고 한다. 되도록 적은 수의 정사각형이 남도록 초콜릿을 쪼개보자. 이때, 버리는 초콜릿이 있으면 안 된다.
위의 그림은 N이 3이고, M이 4인초콜릿이다. 왼쪽 초콜릿은 총 6개의 초콜릿으로 쪼갠 그림이고, 오른쪽 그림은 4개로 쪼갠 그림이다. 오른족 그림이 가장 적은 수의 정사각형으로 쪼개는 방법이다.
초콜릿의 크기가 주어졌을 때, 쪼개서 나올 수 있는 정사각형 개수의 최솟값을 구하는 프로그램을 작성하시오.
첫째 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 1000)
첫째 줄에 초콜릿을 쪼개서 나올 수 있는 정사각형 개수의 최솟값을 출력한다.
3 4
4
4 4
1
2 5
4
Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Exam #1 2번