자리 배정(방 배정하기) timer 1s memory 256MB

N 개의 자리가 왼쪽부터 오른쪽으로 일렬로 늘어서 있다.

자리 번호는 가장 왼쪽이 1번 가장 오른쪽이 N번이다.

이제 1 ~ N까지 번호를 가진 학생들에게 1번 학생부터 차례로 자리를 배정한다.

자리를 배정하는 규칙은 다음과 같다.

1. 연속한 빈 공간 중에 가장 큰 구간을 찾고 그 구간의 가운데 자리에 학생을 앉힌다. 자리를 찾는데 소수가 등장하면 소수점 이하는 버림한다.

2. 연속한 빈 공간 중에 가장 큰 구간이 두 개 이상인 경우, 자리 번호가 작은 것을 찾아 배정한다.​

예를 들어 N이 6인 경우를 보자.

다음 # 6개는 아직 빈 자리를 뜻한다.

공백은 자리와 자리를 구분하기 위한 용도이다.

# # # # # #

1번 학생은 (1+6) / 2 = 3(소수점이하는 버림)이므로 3번자리에 앉는다.

# # 1 # # #

2번 학생은 4~6 구간이 가장 크므로 (4+6) / 2 = 5번자리에 앉는다.

# # 1 # 2 #

3번 학생은 1~2 구간이 가장 크므로 (1+2) / 2 = 1번자리에 앉는다.

3 # 1 # 2 #

4번 학생은 가장 큰 구간이 3개(2번 자리, 4번 자리, 6번 자리​)가 있다. 

이중 자리 번호가 가장 작은 것은 2번이므로 2번에 앉는다.

3 4 1 # 2 #

5번 학생은 가장 큰 구간이 2개(4번 자리, 6번 자리​)가 있다. 

이중 자리 번호가 가장 작은 것은 4번이므로 4번에 앉는다.

3 4 1 5 2 # 

6번 학생은 남은 한 자리 6번에 앉는다.

3 4 1 5 2 6 

​학생수 N을 입력받아 자리를 배정하는 프로그램을 작성하시오.