원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
거리두기
원제: 거리두기
문제
명의 학생이 수직선 위에 서려고 한다. 수직선에서는 수가 클수록 더 오른쪽에 있는 위치를 나타낸다.
학생들은 번부터 번까지 번호 순서대로 왼쪽부터 오른쪽으로 서며, 학생들이 서는 위치는 모두 정수이다.
번 학생이 서는 위치를 라고 하자. 학생들이 서는 위치는 다음 조건을 만족해야 한다.
- 정수 에 대해, 번 학생은 위치 보다 오른쪽에 설 수 없다. 즉, 여야 한다.
- 번호가 연속한 두 학생은 이상의 거리를 두어야 한다. 즉, 정수 에 대해 여야 한다.
인 경우에는 여러 학생이 같은 위치에 서도 된다.
학생들은 번 학생의 위치 을 가능한 한 크게 만들고 싶다.
조건을 만족하면서 학생들이 수직선 위에 서는 방법 중 의 값이 가장 큰 방법을 구하라. 그러한 방법이 여러 개라면 그중 아무거나 구하라.
조건을 만족하면서 학생들이 수직선 위에 서는 방법이 적어도 하나는 존재함을 증명할 수 있다.
제약 조건
- 주어지는 모든 수는 정수이다.
- 정수 에 대하여
부분문제
- (25점) 정수 에 대해 이다.
- (35점)
- (30점) 조건을 만족하도록 학생들이 서는 방법 중 인 것이 존재한다.
- (10점) 추가 제약 조건 없음.
입력 형식
첫 줄에 두 정수 과 가 공백으로 구분되어 차례대로 주어진다.
그다음 줄에 개의 정수 이 공백으로 구분되어 차례대로 주어진다.
출력 형식
첫 줄에 개의 정수 을 공백으로 구분하여 출력한다. 이때, 학생들이 수직선 위에 서는 방법 은 지문에서 주어진 모든 조건을 만족해야 하며, 의 값이 최대화되어야 한다.
가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.
예제
예제 1
5 2 1 4 10 9 13
1 4 6 9 12
예제 2
4 0 5 2 7 3
2 2 3 3
예제 3
4 3 2 1 5 9
-2 1 5 8