바닥 장식
시간 제한2초메모리 제한128 MB
무한히 반복되는 1x5 널판 타일 무늬에서 직사각형 영역을 잘라낼 때, 그 안의 조각을 모두 만들기 위해 사야 하는 1x5 널판의 최소 개수를 구한다.
문제
방 바닥을 꾸미기 위해 다음과 같은 무한한 평면 무늬를 생각해 보자. 이 무늬는 1x5 크기의 나무 판으로 이루어져 있다. 가장 왼쪽 위 좌표는 (0, 0)이고, x좌표는 왼쪽에서 오른쪽으로, y좌표는 위에서 아래로 증가한다.
이 무늬에서 왼쪽 위 꼭짓점이 (x1, y1), 오른쪽 아래 꼭짓점이 (x2, y2)인 직사각형 영역을 선택해 방 크기에 맞는 모양을 만들려고 한다.
근처 상점에서는 1x5 크기의 나무 판만 판매한다. 1x3이나 1x2처럼 더 짧은 판은 1x5 판을 적절히 잘라 만들면 된다. 예를 들어, 1x5 판 하나를 잘라 1x3 판 하나와 1x2 판 하나를 만들 수 있고, 1x2 판 두 개와 1x1 판 한 개를 만들 수도 있다.
위 그림은 (x1, y1)이 (8, 5)이고 (x2, y2)가 (20, 16)인 경우이다. 이때 1x5 판 조각 23개, 1x2 판 조각 6개, 1x1 판 조각 5개가 필요하다. 따라서 나무 판 27개를 사면 충분하다.
x1, y1, x2, y2가 주어질 때 구매해야 하는 나무 판 개수의 최솟값을 구하라. 필요 없는 조각은 버려도 된다.
입력
첫째 줄에 네 정수 x1, y1, x2, y2가 주어진다.
출력
구매해야 하는 나무 판 개수의 최솟값을 출력한다.
제한
- 0 <= x1 < x2 <= 1,000,000
- 0 <= y1 < y2 <= 1,000,000