저는 100 나오네요.

@kesakiyo

질문 하나만 더 할게요.

가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

문제의 한 문장인데요,

10000으로 배정을 해도 전혀 문제가 없지 않나요?

제가 문제이해를 잘못한건가요?

뭔가 얘기를 할려고 했는데 억셉을 받으셨네요ㅋㅋ

ㅋㅋ; 맞추긴했는데 저부분이 아직 이해가 잘 안가는것도 사실이에요.

혹시 정해진 총액 이하에서 가능한 한 최대의 총 예산

여기서 말하는 총액이란게 각각의 예산액수를 말하는건가요?

저는 문제풀때 아무생각없이 당연히 최대값이 각각의 예산들 중 가장 큰 값이라 생각하고 풀었는데

지금 보니까 그 부분에 대한 설명을 못찾겠네요....난독증인가;;

그래서 그냥 KOI 예제 인풋중 하나를 가져왔는데

5

70 80 30 40 100

450

읻때 답이 100 이더라구요.

이 이상은 저도 모르겠네요.

그렇군요. 원래 의도가 100이 뜨는것이 맞는거군요.

두 분다 답변 감사드려요 ㅎㅎ

#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;
// if(min>=temp) min=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;
}

흠... 이 글에 쓰여있는 테스트 케이스 돌려서  다 맞았는데 시간초과 안뜨는데 왜 뭐가 틀렸을까요,, 역시 정답률 29 ㅠㅠ

qkrtjdrb9573

신기한 풀이라 저도 왜 틀린지는 잘 모르겠는데 일단 오류 케이스가 하나 있네요.

3

100 100 100

300

if(real_amount >= M) 

이것이

if(real_amount > M) 

이렇게 되야 고쳐지네요.

그런데 고쳐도 틀림이 뜬다는 함정이..