문제 출처
- 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; }