•
문제의 저작권은 SWEA에 있습니다.
문제
1.
N개의 식재료가 있다.
2.
N / 2개씩 나누어 두 개의 요리 (A, B)
3.
A음식과 B음식의 맛의 차이가 최소가 되도록 재료를 배분해야 한다.
4.
각 음식의 맛은 음식을 구성하는 식재료들로부터 발생하는 시너지 Sij들의 합이다.
5.
A음식과 B음식을 만들 때, 두 음식 간의 맛의 차이가 최소가 되는 경우를 찾고 그 최솟값을 정답으로 출력하는 프로그램을 작성하라.
풀이
1.
N개의 재료로 N/2 개씩 나누어 2개의 요리를 만들어야 하므로 nC(n/2) 을 통해 모든 요리의 경우의 수를 구한다. → next_ permutation
2.
각 조합에 대해 시너지의 합을 구하고 모든 조합의 결과값 중 최소값을 구한다.
a.
시너지의 합을 구하기 위해 2차원 반복문을 통해 nP2 순열쌍을 생성하고, 값을 누적한다.
b.
answer = min(answer , sum)
•
solve 함수
- 모든 (재료 , 재료) 조합에 대해 순열 방식으로 탐색한다.
- 순열 방식으로 동작하기 때문에 모든 순서쌍이 있는 시너지에 대해 값을 구할 수 있다.
- 만약 같은 그룹에 속하는 재료라면 시너지 값을 더한다.
void solve() {
int fst = 0, snd = 0;
for (int i = 0; i < N; i++) { // 모든 재료에 대해 탐색
if (idn[i] == 1) { // 1 그룹에 속하는 재료라면
for (int j = 0; j < N; j++) // 또다른 1 그룹에 속하는 재료에 대해 시너지 Sij 를 누적
if (i != j && idn[j] == 1) fst += arr[i][j];
}else { // 2 그룹에 속하는 재료
for (int j = 0; j < N; j++)
if (i != j && idn[j] == 0) snd += arr[i][j];
}
}
int num = abs((fst - snd)); // num <- 현재의 음식값 차이
answer = min(answer, num); // answer <- 전체 음식값 차이 중 최소값
}
C++
복사
•
Main 함수 동작
int main() {
fastio;
txtcin;
cin >> T;
for (int tc = 1; tc <= T; tc++) {
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> a;
arr[i][j] = a;
}
}
answer = 1e9;
idn.clear();
for (int i = 0; i < N / 2; i++) idn.push_back(0); // next_permutation을 위한 0,1 배열
for (int i = 0; i < N / 2; i++) idn.push_back(1);
do {
solve(); // N/2 , N/2 로 나누어진 음식 그룹 조합에 대해 음식값 차이 구하기 수행
} while (next_permutation(idn.begin(), idn.end()));
cout << "#" << tc << " " << answer << endl;
}
return 0;
}
C++
복사
