시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 128 MB | 398 | 50 | 41 | 16.942% |
방 바닥을 꾸미려고 한다. 다음과 같이 1×5 크기의 나무 판으로 만든 무한한 패턴의 평면을 생각해보자. 가장 왼쪽 위 좌표는 (0,0)이고, X좌표는 왼쪽에서 오른쪽으로 증가하고, Y좌표는 위에서 아래로 증가한다.
이제 이 패턴에서 방 크기와 맞는 구역을 선택할 것이다. 이때 왼쪽 위의 좌표가 (x1, y1)이고, 오른쪽 아래의 좌표가 (x2, y2)인 직사각형 구역을 선택한다. 자 이제 선택한 구역의 모양을 만들 것이다.
하지만, 근처의 상점에서는 오직 1×5크기의 나무 판만 판다. 따라서, 1×3, 1×2크기의 나무 판은 1×5크기의 나무 판을 적절히 잘라서 만들면 된다. 예를 들어, 1×5를 잘라서 1×3과 1×2를 만들 수 있고, 1×2 2개와 1×1 1개를 만들 수도 있다.
위의 그림은 (x1, y1)이 (8, 5)이고, (x2, y2)가 (20, 16)일 때이다. 23개의 1×5와 6개의 1×2, 5개의 1×1이 필요하다. 따라서 27개의 나무 판을 사면 된다.
x1, y1, x2, y2가 주어질 때 구매해야 하는 나무 판의 개수의 최솟값을 구하는 프로그램을 작성하시오. 필요없는 조각은 버려도 된다.
첫째 줄에 네 정수 x1, y1, x2, y2가 주어진다.
첫째 줄에 구매해야 하는 나무 판 개수의 최솟값을 출력한다.
8 5 20 16
27
0 0 5 5
5
0 0 10 2
5
2 2 8 8
12
0 0 1000000 1000000
200000000000