Empty Squares

면접 대비

시간 제한0.1초메모리 제한1024 MB

요약

1xN 보드에 길이 K인 타일 하나가 놓여 있을 때, 남은 서로 다른 길이의 타일들로 겹치지 않게 최대한 많은 칸을 덮고 남는 빈칸 수를 구한다.

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

문제

Martín has a board of $1 \times N$ squares. He also has $N$ tiles of $1 \times 1, 1 \times 2, \dots , 1 \times N$ squares, one of each type. He has placed one of the tiles on the board. His friend, Nico, wants to place some of the remaining tiles in such a way that as many squares as possible are covered. How many squares will remain empty if he succeeds?

Tiles placed on the board cannot overlap each other. Besides, each placed tile must be located completely within the board and must cover whole squares.

입력

The input consists of a single line that contains three integers $N$ ( $1 ≤ N ≤ 1000$ ), $K$ ( $1 ≤ K ≤ N$ ) and $E$ ( $0 ≤ E ≤ N - K$ ), indicating that the board has $1 \times N$ squares, and a tile of $1 \times K$ squares is placed leaving $E$ empty squares to its left.

출력

Output a single line with an integer indicating the number of squares that will remain empty if Nico covers as many squares as possible with the remaining tiles.

예제2

예제 1
입력
```
6 2 2
```
예상 출력
```
3
```
예제 2
입력
```
1000 1 1
```
예상 출력
```
1
```