[codility] MinAbsSum c++

• 문제

 

• 문제 해결

각 원소로 만들 수 있는 합의 개수 구하고,

그 합들을 이용해 전체 합에서 가장 작은 수가 구해질 때 까지 빼나간다.

1. A행렬의 원소를 모두 양수로 전환한다.

    A원소에 1 or -1 곱한 뒤 합을 구하는 거라 A의 원소가 양수여도 상관없다.

2.  양수로 변환된 A행렬의 원소의 합을 구하고 최댓값도 구한다.

    최댓값을 구하는 이유는 각 원소의 개수를 구하는 것이고,

    전체 합을 구하는 이유는 답의 가장 최악의 경우는 전체 합이기 때문

3. 각 원소마다 돌면서 가능한 부분 합들을 구한다.

 이전에 가능한 부분합이 있었다면, 단순히 현재 원소의 개수를 넣어준다.

 처음 만들어진 부분합이라면, 재사용한 것을 표기하기 위해 -1 한다.

4. 부분 합들을 전체합의 절반까지 계산하면서 전체 합에서 2배만큼 빼면서 작은 값을 구하면 답이다.

int solution(vector<int> &A) {
    int nMax = 0, nSum = 0;
    int len = A.size();
    for(int i = 0; i < len; i++){
        int val = abs(A[i]);
        A[i] = val;
        nMax = max(nMax, val);
        nSum += val;
    }

    vector<int> vCnt(nMax+1, 0);
    for(int i = 0; i < len; i++){
        vCnt[A[i]]++;
    }

    vector<int> vSval(nSum+1, 0);
    for(int i = 1; i < nSum+1; i++){
        vSval[i] -= 1;
    }

    for(int i = 1; i < nMax+1; i++){
        if(vCnt[i] > 0){
            for(int j = 0; j < nSum + 1; j++){
                if(vSval[j] >= 0){
                    vSval[j] = vCnt[i];
                }
                else if((j >= i) && (vSval[j-i] > 0)){
                    vSval[j] = vSval[j-i] - 1;
                }                
            }
        }
    }
    int ret = nSum;
    int n = nSum / 2 + 1;
    for(int i = 0; i < n; i++){
        if(vSval[i] >= 0)
            ret = ret < (nSum - (2 * i)) ? ret : (nSum - (2*i));
    }
    return ret;
}