아무것도 만지지 마세요

면접 대비

시간 제한1초메모리 제한32 MB

요약

R행 C열 격자와 한 변이 N인 정사각형이 주어질 때, 격자 밖으로 나가거나 서로 겹쳐도 되도록 정사각형을 놓아 격자 전체를 덮는 최소 개수를 구한다.

난이도: 보통10점 중 4점
유형: 수학, 그리디
정답자: 아직 제출이 없습니다

문제

대회장 좌석은 $R$ 행 $C$ 열의 직사각형으로 배치되어 있다. 대회가 시작하기 전에는 참가자가 아무것도 만지면 안 되므로 진행자가 계속 주의를 준다.

그런데 진행자가 목을 다쳐 더는 소리를 낼 수 없게 되었다. 그래서 주최측은 CCTV를 설치해 참가자를 감시하기로 했다. CCTV 한 대는 $N$ 행 $N$ 열의 직사각형 영역에 있는 좌석을 촬영한다. CCTV는 좌석 배치와 같은 방향으로만 놓을 수 있고, 촬영 범위가 좌석 바깥으로 나가거나 다른 CCTV의 범위와 겹쳐도 된다.

모든 좌석이 적어도 한 대의 CCTV에 촬영되도록 배치할 때, 필요한 CCTV의 최소 개수를 구하라.

입력

첫째 줄에 좌석의 세로 크기 $R$ , 가로 크기 $C$ , 그리고 CCTV 한 대가 촬영하는 범위 $N$ 이 공백으로 구분되어 주어진다. ( $1 \le R, C, N \le 1\,000\,000$ )

출력

모든 좌석을 촬영하는 데 필요한 CCTV의 최소 개수를 한 줄에 출력한다.

예제5

예제 1
입력
```
7 9 3
```
예상 출력
```
9
```
예제 2
입력
```
1 1 1
```
예상 출력
```
1
```
예제 3
입력
```
1 1 1000000
```
예상 출력
```
1
```
예제 4
입력
```
10 10 3
```
예상 출력
```
16
```
예제 5
입력
```
5 1 2
```
예상 출력
```
3
```