빈 칸

면접 대비

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

요약

보드 길이 N, 배치된 타일 길이 K, 왼쪽 빈칸 수 E가 주어질 때 나머지 타일로 최대한 덮고 남는 빈칸 수를 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

마틴은 $1 \times N$ 크기의 보드를 가지고 있다. 그는 $1 \times 1, 1 \times 2, \dots , 1 \times N$ 크기의 타일을 종류별로 하나씩, 모두 $N$ 개 가지고 있다. 마틴은 그중 타일 하나를 이미 보드에 놓았다. 그의 친구 니코는 남은 타일 일부를 놓아 가능한 한 많은 칸을 덮으려 한다. 니코가 성공한다면 빈 칸은 몇 개가 남는가?

보드에 놓인 타일끼리는 겹칠 수 없다. 놓는 각 타일은 보드 안에 완전히 들어가야 하며, 칸 단위로 빈틈없이 덮어야 한다.

입력

입력은 한 줄이며, 세 정수 $N$ ( $1 \le N \le 1000$ ), $K$ ( $1 \le K \le N$ ), $E$ ( $0 \le E \le N - K$ )가 주어진다. 보드는 $N$ 칸이고, $K$ 칸짜리 타일이 왼쪽에 빈 칸 $E$ 개를 남기고 놓여 있다.

출력

니코가 남은 타일로 가능한 한 많은 칸을 덮었을 때 남는 빈 칸의 수를 한 줄에 출력한다.

예제2

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