알고리즘은 다음과 같이 작성했습니다.

1. 입력 받음

2. 퀵 소트로 오름차순으로 정렬

3. 정렬된 배열 a[0].a[1],a[2]....a[n-1]이 있을 때,

전체의 합을 sum, 예산 최대치를 k라고 지정.

만약 sum보다 k가 클 때는 a[n-1]이 무조건 답

만약 a[0]*n보다 k가 작거나 같을 경우, k/n이 답.

(만약 a[0]=110, a[1]=120..... 에 k가 550일 경우, 550/5=110이 답. 혹은 a[0]=110, a[1]=120...에 k=500일 경우 500/5=100이 답.)

만약 그 둘 다 아닌 경우,  else문 내의 알고리즘을 수행하며 그 순서는 다음과 같습니다.

int total=0//각 경우의 합을 받아올 변수.

int index//각 경우에서 최대의 배열 번호를 받아올 변수

int x//각 경우의 합을 계산받은 후 total을 갱신할 변수

1. i의 값을 증가시키며, i=0부터 i=n-1까지는 요구 금액이 변하지 않을 경우의 근사치를 구한다.

(index=1이면 a[0],a[1]의 요구 금액은 항상 충족된다는 뜻. index=2부터 변화 가능성 소지)

2. 해당 근사치가 예산 총액 미만이고, 이전에 구한 최대 근사치보다 클 때 total을 갱신

3. 해당 작업을 반복

4. 모두 반복 후, index까지는 안전하므로 a[index+1]부터 a[n-1]까지의 모든 배열 값을 a[index+1]로 변경

5.배열의 총합 구함

6. (예산-배열 총합)의 계산 해 sub에 배정 후 index+2부터 n-1까지의 배열에 예산이 차감된 배열의 수만큼 sub을 나눠 sub2에 배정

7. 차감된 배열들에 sub2를 더함

본 알고리즘을 사용해 테스트 케이스인

4/120,110,140,150/485 수행 시

110 120 140 150 정렬

index=0

a[index+1]=120

index+1부터 n-1(4)까지 120으로 갱신

110 120 120 120

이후 전체의 합인 470을 예산 총액인 485에서 차감

int sub=15

변동된 배열의 수는 2개이므로

int sub2=15/2=7

변동된 배열에 더할 경우 

110 120 127 127

로 127이 제대로 나왔습니다.

뭐가 문제일까요?