cho.sh레모네이드 줄서기
각 소가 견딜 수 있는 최대 대기 인원이 주어질 때, 줄에 남는 소의 수가 최소가 되도록 도착 순서를 정한다.
보통4그리디정렬배열구현면접 대비아직 제출이 없습니다시간 제한2초메모리 제한512 MB문제
무더운 여름날, 농부 존이 소 N마리에게 레모네이드를 나눠 주려고 한다. 소는 모두 레모네이드를 좋아하지만 좋아하는 정도는 저마다 다르다. 1번부터 N번까지 번호가 붙어 있고, i번 소는 자기 앞에 최대 wi마리까지 서 있어야 줄을 서서 기다린다.
지금 소는 모두 들판에 있다. 존이 종을 울리면 소들은 곧바로 레모네이드 가판대로 몰려온다. 존이 레모네이드를 나눠 주기 전에 소가 모두 도착하고, 두 소가 같은 시각에 도착하는 일은 없다. i번 소는 도착한 순간 줄에 서 있는 소가 wi마리 이하이면 줄을 서고, 그보다 많으면 그냥 돌아간다.
존은 레모네이드를 미리 준비하려 하지만 낭비하고 싶지는 않다. 줄을 서는 소의 수는 도착 순서에 따라 달라진다. 가능한 모든 도착 순서를 따질 때 줄을 서는 소가 가장 적은 경우의 마릿수를 구하여라.
입력
첫째 줄에 N이 주어진다. 둘째 줄에 N개의 정수 w1,w2,…,wN이 공백으로 구분되어 주어진다. 1≤N≤105이고, 각 소에 대해 0≤wi≤109이다.
출력
가능한 모든 도착 순서 가운데 줄을 서는 소가 가장 적은 경우의 마릿수를 한 줄에 출력한다.
힌트
첫 번째 예제에서는 세 마리만 줄을 서고, 이보다 적게 만드는 순서는 없다. w가 7인 소와 400인 소가 먼저 도착해 줄을 선다고 하자. 이어서 w가 1인 소가 도착하지만 이미 두 마리가 서 있어 돌아간다. 마지막으로 w가 2인 소 두 마리가 도착해 한 마리는 줄을 서고 한 마리는 돌아간다.