개의 항을 가진 수열 가 있다. 각 항에 을 더하거나 빼는 연산을 수행할 수 있다. 같은 항에 연산을 여러 번 수행하는 것도 가능하다.
최소한의 연산으로 수열 에서 어떤 값 가 번 이상 등장하도록 만드는 프로그램을 작성하라. 번 이상 등장하는 값이 개 이상이어도 상관 없다.
입력 형식
첫 줄에 수열의 길이를 나타내는 정수 과 정수 가 주어진다. ()
그다음 줄에 수열의 개의 항의 초깃값이 공백으로 구분되어 차례대로 주어진다. 이 값은 모두 이상 이하의 정수다.
출력 형식
첫 줄에 최소 연산 횟수를 출력한다.
예제
입력
5 4 2 1 2 4 2
출력
1
예제 설명
첫 번째 예제에서, 한 번의 연산으로 수열의 두 번째 값을 로 바꾸면, 수열은 가 되어 가 번 등장하게 된다.
채점 방식
입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞혀야 그 종류에 배정된 점수를 받을 수 있다.
종류 1: 13점
수열의 항의 초깃값은 모두 이상 이하이다.
종류 2: 26점
종류 3: 61점
모든 입력 케이스가 주어진다.
해설
입력된 수를 오름차순으로 정렬한 뒤 구간을 모두 같은 값으로 만드는 전략을 사용할 것입니다.
오름차순으로 정렬된 개의 수 을 모두 어떤 값 로 만들기 위해서는 만큼의 연산이 필요합니다. 함수 는 처음에는 계속 감소하다가 특정 지점 이후부터는 계속 증가하는 형태의 함수이며, 극소점을 갖는 지점은 의 중앙값입니다.
따라서 개의 수를 그들의 중앙값, 다시 말해 으로 만드는 것이 최적입니다. 를 총 개의 구간에 대해 계산해야 하고, 이는 누적합 배열을 이용해 매번 상수 시간에 계산할 수 있습니다. 입력으로 주어진 수를 오름차순으로 정렬하는 데 , 이후 의 값을 계산하는 데 만큼의 연산이 필요하므로 전체 시간 복잡도는 입니다.