스타트와 링크 14889번 (삼성전자 채용 시험)

https://www.acmicpc.net/problem/14889

일단 사전 작업을 해준다.

1. 대각선에 있는 것끼리 더해서 한 쪽으로 몰아준다
어차피 대각선에 있는 것끼리 더하는 작업을 하게 되기 때문이다/

    //더하고 0으로 초기화
    for (int i = 0; i < N ; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i < j){
                matrix[i][j] += matrix[j][i];
                matrix[j][i] = 0;
            }
        }
    }

2. (N/2)명씩 팀을 짜야한다.

이 부분을 반복문으로 하는 건 힘들다.
4명까지는 몰라도 20명은 정말 힘들다.

그러므로 재귀호출을 통해서 combine을 구현해야 한다.
정확히 기억이 나지 않아서 다시 알고리즘 문제풀이 책을 펼쳐 보았다

void pick(int n, vector<int> element , int toPick, int *min)
{
	//터미널 조건
	if (toPick == 0){
		return;
	}
	int smallest = element.empty() ? 1 : element.back() + 1;

	for (int i = smallest ; i <= n; i++)
	{
		element.push_back(i);
		pick(n, element, toPick - 1, min);
		element.pop_back();
	}
}

위 코드는 조합을 구현한 것을 나타낸다.

//선택된 요소을 제외한 나머지 요소들 공식 적용
		for (int i = 0; i < (n / 2) - 1; i++)
		{
			num1 = element2.at(i);
			for (int j = i + 1; j < n / 2; j++)
			{
				num2 = element2.at(j);

				cnt2 += matrix[num1 - 1][num2 - 1];
			}
		}

위 코드는 선택된 (N/2)명을 제외한 나머지 (N/2)를 팀으로 짠 것이다.

ex) (1,2,3,4)가 한팀이면 (5,6,7,8)이 한팀이다.

 

3. 팀을 나눈 후 그 팀들의 점수를 구한다.

//선택된 조합을 가지고 공식 적용
		for (int i = 0; i < (n/2) - 1; i++)
		{
			num1 = element.at(i);
			for (int j = i + 1; j < n/2; j++)
			{
				num2 = element.at(j);
				cnt1 += matrix[num1 - 1][num2 - 1];
			}
		}

선택된 element를 가지고 공식을 적용하는 공식이다.
이는 자주 쓰이므로 함수로 만들어 사용하는 것이 좋다.

 

 

//abs구현
		int res = cnt1 - cnt2;
		if (res < 0)
			res = -res;

		//min업데이트
		if (*min > res)
			*min = res;

합산된 점수를 비교한다.
절댓값과 최솟값 비교가 필요하다.