#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

   ......

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

yukariko   2년 전

전에도 한번 말씀 드렸는데 이 소스에다가 케이스로

3

100 100 100

300

을 주면 99가 출력되서 틀림이 됩니다.

물론 이걸 고쳐도 틀림이 뜨는건 마찬가지이긴 한데 어찌됬든 틀린 케이스중 하나지요..

yukariko   2년 전

그리고 소스를 올리는 경우엔 글쓰기 기능중에 소스 추가를 이용해주세요. 그래야 다른분들이 소스를 긁어다 테스트해 볼 수 있으니까요.

아 넵 감사합니다. 바로 수정하겠습니다.

근데 그거 고쳐도 계속 틀렸다고 나오네요... 하 뭐가 문젤까요?

hujub   2년 전

real_amount -= arr[max];

단위 문제인것 같습니다.

real_amount 는 전체 예산의 양인데 여기다가 arr[max] 즉, max의 개수를 빼주니깐.. 단위가 안맞네요.

예를들어,arr[max]*max 이렇게 해야 단위가 맞을것 같습니다.

게다가

max = max-1;

이 부분도 이상합니다.

인풋 데이터로

4

120 100 100 165

485

이게 답이 165 인데.

real_amount 에서 arr[165] 를 뺀 후 바로 max = max - 1; 시켜버리니깐..

164..

163..

답이랑 멀어지네요. 다시 한번 푸는 방법을 점검해보시는게 좋을것 같습니다..

아 정말 감사합니다.

댓글을 작성하려면 로그인해야 합니다.