[[problem:QUANTIZE]] 문제를 풀다가 왜 이런 결과가 되는지 궁금해서 질문드립니다....

제 알고리즘은
1. 수열을 받아서 크기 순서대로 정렬
2. group 배열과 elem_cnt 배열 을 하나 만들고, 양자화 할 수 있는 값들을 저장 시킵니다.
3. 수열 값을 읽으면서 group에 값을 넣는데, 양자화 할 수 있는 수를 넘게 되면 최소 차이나는 값들을 하나의 값으로 합칩니다.
그 합친 값들에 해당하는 elem_cnt를 하나 증가시킨다.
4. 수열이 끝날때까지 연산을 계속한다.
5. calculate()를 통해 오차값을 구합니다.

Input :
1
9 3
1 744 755 4 897 902 890 6 777

Output :
650

(정답은 651)

calculate() 함수 내에서 값을 하나하나 찍어보니 이곳에서 오류가 발생했는데 이유를 모르겠습니다.

• ret=13, arr[3]=744, group[1]=759, pow(arr[i]+group[j],2)=225, ret + pow(arr[i]+group[j])=238

• ret=237, arr[4]=755, group[1]=759, pow(arr[i]+group[j],2)=16, ret + pow(arr[i]+group[j])=253

15² = 225 에 13을 더하면 238인데 ret가 237로 바꼈습니다...

제가 만든 calculate() 함수에서 ret 덧셈연산중 1오차가 생기는 것이 발생하여서 질문합니다. 제 코드를 돌리다보면 side effect가 생겨서 1의 오차가 생기는 것인지 아니면 연산중에 제가 1을 빼는 것인지 궁금합니다. 고수님들 가르쳐주세요..ㅠ
아래는 소스코드입니다.
~~~ c++
#include
#include
#include
#include

using namespace std;

#define INF 100000000000;

int compare(const int &a, const int &b)
{
if(a <= b) return 1;
else return 0;
}

void printArr(vector& arr)
{
cout << "[";
for(int i=0;i cout << arr[i] << " ";
cout << "]" << endl;
}
void printArr1(vector& arr)
{
cout << "[";
for(int i=0;i<arr.size();i++)
cout << arr[i] << " ";
cout << "]" << endl;
}

int getLowest(vector &group)
{
double value = INF;
int ret = -1;
for(int i=0;i {
if(group[i] == group[i+1])
return i;
if(value > group[i+1]-group[i])
{
value = group[i+1]-group[i];
ret = i;
}
}
return ret;
}

void mergeGroup(vector &group, vector &elem_cnt, int index)
{
int elem = group[index+1];
int cnt = elem_cnt[index+1];

// cout << "elem=" << elem << ",cnt="<< cnt << endl;
group[index] = group[index]*elem_cnt[index] + elem*cnt;
elem_cnt[index] += elem_cnt[index+1];

group[index] /= elem_cnt[index];
group.erase(group.begin()+index+1);
elem_cnt.erase(elem_cnt.begin()+index+1);

}

int calculate(vector &arr, vector& group, vector&elem_cnt)
{

printArr(group);
printArr1(elem_cnt);
int ret = 0;
int j=0;
for(int i=0;i<arr.size();i++)
{
    if(elem_cnt[j] == 0)
        j++;


    if(group[j] - (int)group[j] > 0.5)
        group[j] = (int)group[j] + 1;
    else group[j] = (int)group[j];

    cout <<"ret=" << ret ;
    cout <<", arr["<<i<<"]=" << arr[i] ;
    cout <<", group["<<j<<"]=" << (int)group[j];
    cout <<", pow(arr[i]+group[j],2)=" << pow(arr[i] - (int)group[j], 2) ;
    cout <<", ret + pow(arr[i]+group[j])=" << ret + pow(arr[i] - (int)group[j], 2)<<endl;
    ret += pow(arr[i] - (int)group[j], 2);

    elem_cnt[j]--;
}
return ret;

}

int quantization(vector &arr, int groupSize)
{
vector group;
vector elem_cnt;

stable_sort(arr.begin(),arr.end(),compare);
//printArr1(arr);

for(int i=0;i<arr.size();i++)
{
    group.push_back((double)arr[i]);
    elem_cnt.push_back(1);

    if( group.size() > groupSize)
    {
        int index = getLowest(group);

        mergeGroup(group,elem_cnt,index);
    }
}

return calculate(arr,group,elem_cnt);

}

int main()
{

int num;
int arrSize;
int testcase;
int groupSize;
vector<int> arr;

cin >> testcase;

while(testcase--)
{
    cin >> arrSize >> groupSize;

    for(int i=0;i<arrSize;i++)
    {
        cin >> num;
        arr.push_back(num);
    }

    cout << quantization(arr,groupSize) <<endl;

    arr.clear();
}
return 0;

}