#include<stdio.h>
int main() {

int arr[111111]={0,};
int M,N,i,temp,max=0,real_amount=0;
scanf("%d", &N);
for(i=0; i<N; i++) {
scanf("%d", &temp);
real_amount+=temp;
arr[temp] += 1;
if(max<=temp) max=temp;
}

scanf("%d", &M);
while(1) {

if(real_amount > M) {

real_amount -= arr[max];
max = max-1;
arr[max] += arr[max+1];
arr[max+1] = 0;

} if(real_amount <= M) break;

}

printf("%d\n", max);

return 0;
}

일단, 제 풀이 부터 설명 드리겠습니다. 제 풀이는 먼저 입력된 숫자를 모두 받아서 배열에 그 숫자에 해당하는 곳에 저장합니다. 예를 들어 요청한 예산이 127이라면 arr[127]에 1을 저장하는 것이지요. 저장이 끝나면 max값을 찾습니다. 만약 모두 더한 값(real_amount)이 총예산 보다 크면 max값에서 배열에 저장된 값중 제일 큰 값을 뺍니다. 그리고 하나 아래의 배열에 뺀 크기 만큼 저장합니다. 이것 역시 예를 들어 설명하면

3

148 147 146

300

이라고 가정을 해봅시다. 그러면 148이 arr[148]에 저장이 되어 있겠죠. 그러면 상한값을 찾기 위에 148을 1만큼 줄여나가게 되는데 이때 1만큼 출이면 arr[148] = 0 이 되고 arr[147] = 2 가 됩니다. 그리고 그 다음엔 arr[147] = 0 이 되고 arr[146] = 3이 되겠죠. 이렇게 계속 줄여나가면

1) 148 147 146

2)147 147 146

3)146 146 146

4)145 145 145

   ......

이런 식으로 쭉 내려가면서 이 예산들의 합이 총예산보다 작아지는 순간 출력을 하도록 코딩하였는데 문제는 자꾸 틀렸다고 나온다는 겁니다. 부디 왜 이런 일이 생기는지 답변 부탁드립니다. 항상 성의껏 답변해주시는 분들에게 정말 감사드립니다.