[AC] 2512 예산

출처 : https://www.acmicpc.net/problem/2512

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.01/2512.cpp

이 문제는 정보올림피아드 다운 문제였다. 어렵진 않지만 귀찮은 문제였다. 먼저 문제의 키포인트부터 보자.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다. 

첫번째 조건을 살펴보면 즉 이런말이다. 입력으로 들어온 n을 다합쳐도 m으로 입력한 값보다 작거나 같으면 요청한 금액을 그대로 집행한다는 말이다. 

두번째 조건은 상한선을 둔다는 말인데, 요청한 금액이 적은녀석들은 그대로 두면서 높은 요청은 전부 동일한 상한선을 두어 나눠준다는 말이다.

읽자마자 나누기가 생각났다. 이유는 모르겠다.

나의 알고리즘은 다음과 같다.

1. 입력값을 먼저 정렬해준다.

2. 입력값의 총 합과 m을 비교후 m이 더크거나 같으면 정렬된 값의 맨 마지막을 출력한다.(문제는 가장 큰값을 출력하라고 했다.)

3. 그 외의 경우에는 요소 하나를 m에서 빼고 나머지 값을 현재 남은 요청수대로 나눠준다. 근데 이 값이 만약 현재 요청값보다 크다면 그 값을 채택한다. 

만약 요청값보다 작다면 버려지는 금액이 발생하기 때문에 더 배정할 수 있다는 말이 된다. 
(이런 생각을 왜 했냐고 물으면 나도 모른다. 생각이 났다.)

4. 하지만 m값에서 요청한 n을 나눈값이 만약 채택한 값보다 크다면 m에서 n을 나눈 값을 출력한다. 그게 아니라면 3번에서 채택한 값을 출력한다.

왜냐면 만약 요청값이 전부다 크고, m값이 작을때는 채택한 값보다 단순히 나눠준값이 더 클수도있다. 그렇기 때문에 이런 조건을 추가해줘야한다.  이걸 찾는데 상당한 시간을 허비했다. 보통의 경우는 이런식으로 나눠주면 모든 요소에 공통적으로 배분할수있도록 값이 나오는데 당연히 그값은 크지 않다. 

정보 올림피아드 문제는 풀때마다 생각하지만, 항상 까다롭고 귀찮은 예외 케이스가 존재한다. 이걸 한번에 생각하고 코딩하거나 그런 예외따위 무시하게만들면 최고의 알고리즘이지만 이처럼 예외가 발생하는 경우가 허다하다. 혼자 예제만드는 것또한 기술이라고 생각한다.