[EPPER] 9회 8번

문제

 

 

 

---

풀이

 

백트래킹 문제다. 도대체 어디에 백트래킹이 들어가냐고 물어본다면 팀 나눌 때 들어간다. 백준에서 비슷한 문제를 풀 때는 친절하게 인원은 모두 짝수라고 했었는데, 여긴 홀수도 있다. 뭐...그렇게 크게 달라진 부분은 없다.

 

 

 

promising한 노드만 적었다. promising의 조건은 상위 노드보다 큰 index여야 한다는 것이다. 왜냐면 (0,1)/(2)랑 (1,0)/(2)는 차이가 없기 때문이다. 이런 방법으로 중복을 제거하면 조합같이 보인다.

이를 구현하기 위해 make_team 함수의 인자가 2개인 것이다. now는 상위 노드의 인덱스값을 알기 위해 사용하고, cnt는 그래서 지금 팀에 몇 명이 모였는지 알기 위해서 사용한다. 그러니 메인에서의 호출도 make_team(0, 0)인 것이다. 0번 인덱스부터 시작하고 현재 팀에는 아무도 없으니까. 아무튼 이 과정으로 team에 들어간 index는 isTeam을 true 체크한다. 팀 쪼개기는 (팀의 멤버 수(cnt))==(n/2)일 때 끝난다.

 

팀을 쪼갰으면 각 팀의 몸무게를 계산할 차례이다. 편의상 isTeam이 true로 체크된 멤버는 team1로 그렇지 않은 멤버는 team2로 칭한다. team1의 무게와 team2의 무게를 계산했으면 일단 두 무게를 비교한다. 최종에서 작은 값부터 출력해야하기 때문에 team1의 무게가 team2보다 작은지 확인하는 것이다. 그리고 이 둘의 차이가 현재의 최소값보다 작다면 해당 값으로 최소값을 갱신한다.

---

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>

int weight[100];
bool isTeam[100] = { 0, };
int n, min = 1000000;
int team1_min, team2_min;

void make_team(int now, int cnt) {
	if (cnt == n / 2) { //절반 쪼개면 계산
		int team1_w = 0, team2_w = 0;

		for (int i = 0; i < n; i++) {
			if (isTeam[i]) //isTeam 체크됐으면 team1 이라는 것
				team1_w += weight[i];
			else
				team2_w += weight[i];
		}
		if (team1_w > team2_w) { //작은 순서로 출력해야 하니까 확인
			int temp = team1_w;
			team1_w = team2_w;
			team2_w = temp;
		}
		if (team2_w - team1_w < min) { //최소값보다 작으면
			min = team2_w - team1_w;
			team1_min = team1_w;
			team2_min = team2_w;
		}
	}
	else { //백트래킹으로 팀 쪼개기
		for (int i = now; i < n; i++) {
			isTeam[i] = true;
			make_team(i + 1, cnt + 1);
			isTeam[i] = false;
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &weight[i]);
	make_team(0, 0);
	printf("%d %d", team1_min, team2_min);
}