[Algorithm] 요리사 (SW Expert Academy – 4102)

문제 출처

• https://www.swexpertacademy.com

난이도

• (하) – 중 – 상 – 최상 – 풀지 못함

문제 (항상 대략적인 설명만 작성합니다. 문제는 위 출처에서 확인하세요)

• 여러 개의 음료 재료가 Input으로 주어진다. 여러 가지 재료를 딱 반으로 나누어 음식을 만들었을 때 음식의 맛이 차이를 최소화하는 방법을 계산하는 문제이다.
• SW Expert Academy의 경우 문제 공개를 하면 안 된다고 되어있어서 더 상세히 문제를 작성하지 않았다. 상세한 내용은 위 사이트에서 확인 부탁합니다.

후기

• 개인적으로 SW Expert Academy 모의 검정고시 문제 중 제일 쉬운 문제라고 생각한다.
• Recursive 함수를 사용하여 모든 재료의 조합을 만든다. Recursive 함수의 기저 사례 부분에서 두 음식의 맛의 값을 계산하고, 마지막으로 두 음식 맛의 값을 차이를 저장해두면 된다.

코드

• Recursive 함수를 사용하여 모든 경우의 수를 계산하는 코드
• 실행 시간: 61ms (제일 빠른 코드 대비 4배(15ms) 느림)

#include <stdio.h>

//MK: Visual Studio를 사용시 scanf 에러 제거함.
#pragma warning(disable: 4996) 

#define MAXSIZE 16

#define MIN(a,b) (a)<(b)?(a):(b)
#define ABS(a) ((a)<0?-(a):(a))

int inputList[MAXSIZE][MAXSIZE];
int inputSize;

int foodA[MAXSIZE / 2];
int foodB[MAXSIZE / 2];
int numFoodA;
int numFoodB;

int finalAnswer;

//MK: foodA와 foodB의 맛 차이를 계산하는 코드
int diff() {
	int sumA = 0; 
	int sumB = 0;
	for (int i = 0; i < inputSize / 2; i++) {
		for (int j = i; j < inputSize / 2; j++) {
			sumA += inputList[foodA[i]][foodA[j]];
			sumA += inputList[foodA[j]][foodA[i]];
			sumB += inputList[foodB[i]][foodB[j]];
			sumB += inputList[foodB[j]][foodB[i]];
		}
	}
	return ABS(sumA - sumB);
}

//MK: List를 사용해서 FoodA/FoodB를 나누는 코드
//MK: 모든 경우의 수를 계산함.
void findMin(int foodNum) {
	if (foodNum == inputSize) {
		int tmp = diff();
		finalAnswer = MIN(finalAnswer, tmp);
		return;
	}
	if (numFoodA < inputSize / 2) {
		foodA[numFoodA] = foodNum;
		numFoodA++;
		findMin(foodNum + 1);
		numFoodA--;
	}
	if (numFoodB < inputSize / 2) {
		foodB[numFoodB] = foodNum;
		numFoodB++;
		findMin(foodNum + 1);
		numFoodB--;
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	int testCase = 0;
	scanf("%d", &testCase);
	for (int m = 1; m <= testCase; m++) {
		scanf("%d", &inputSize);
		numFoodA = 0;
		numFoodB = 0;
		finalAnswer = 20000 * 2 * inputSize + 1;
		for (int i = 0; i < inputSize; i++) {
			for (int j = 0; j < inputSize; j++) {
				scanf("%d", &inputList[i][j]);
			}
		}
		findMin(0);
		printf("#%d %d\n", m, finalAnswer);
	}
	return 0;
}