글 읽기 - n이 4, 6일땐 맞는데 8에서 틀립니다.

zaitplan 3년 전 0

memberRef는 이중벡터로 각 선수간의 시너지 포인트가 저장됩니다. pair로 Combination의 편의성을 고려했습니다.

member는 0번 선수, 1번 선수 ,... n-1번선수처럼 쓸 예정입니다.

com, comRef는 각각 Combination을 할 때 무엇을 골랐는지 기록하기 위해 만들었습니다.

1. n x m의 zero base 이중벡터에각 선수끼리의 포인트를 받습니다.

2. n명이 있다면 n / 2 명을 combination합니다. 이렇게 뽑힌 사람들을 대충 team start에 두면

n - 1 - i(i는 0부터 시작), n - 1 - (i + 1), ... 이런 식으로 남은 team link의 사람들의 index를 찾을 수 있다고 생각했습니다.

3. front에 team start의 총 합을 넣고 team link 도 구하고 절댓값을 찾아 비교하면 된다고 생각했는데 n = 4, n = 6일때는 테스트케이스를 통과하는데 n = 8일떈 테스트 케이스를 통과하지 못합니다.긴 시간생각해봤는데 잘 모르겠씁니다. 도움을 부탁드입니다.

#include <iostream>
#include <vector>
constexpr int MAX = 20;
// Acutual number of members. Zero based indexing
std::vector<std::pair<int, bool>> member;
std::vector<std::vector<int>> memberRef(MAX, std::vector<int>(MAX));
std::vector<std::pair<int, bool>> com, comRef;
int minAbsVal(2000001);


void Com(int _curIdx, int _max, int _r)
{
    if(_max / 2 == _r)
    {
        // Divide combination vector into two team
        int frontVal(0), backVal(0);
        for(int i = 0; i < _max / 2; i ++)
        {
            for(int j = i; j < _max / 2; j++)
            {
                frontVal += memberRef.at(com.at(i).first).at(com.at(j).first);
                frontVal += memberRef.at(com.at(j).first).at(com.at(i).first);
                backVal += memberRef.at(_max - 1 - com.at(i).first).at(_max - 1 - com.at(j).first);
                backVal += memberRef.at(_max - 1 - com.at(j).first).at(_max - 1 - com.at(i).first);
            }
        }
        
        if (minAbsVal > std::abs(frontVal - backVal)) 
        {
            minAbsVal = std::abs(frontVal - backVal); 
        }
        return;
    }
    else
    {
        for(int i = _curIdx; i < _max; i++)
        {
            if(!member.at(i).second)
            {
                member.at(i).second = true;
                com.push_back(member.at(i));
                Com(i + 1, _max, _r + 1);
                com.pop_back();
                member.at(i).second = false;
            }
        }
    }
}
int main(void)
{
    int n(0); // 4 <= n <= 20
    
    std::cin >> n;
    for(int i = 0; i < n; i++)
    {
        member.push_back({i, false});
        for (int j = 0; j < n; j++)
        {
            std::cin >> memberRef.at(i).at(j);
        }
    }
    
    Com(0, n, 0);
    std::cout << minAbsVal; 
    
    return 0;
}

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