[SWEA]요리사 - 4012 (모의 역량 테스트)
| 시간 제한 | 메모리 제한 |
|---|---|
| 10 초 | 힙 정적 메모리: 256 MB / 스택 메모리 1MB |
문제
두 명의 손님에게 음식을 제공하려고 한다.
두 명의 손님은 식성이 비슷하기 때문에, 최대한 비슷한 맛의 음식을 만들어 내야 한다.
N개의 식재료가 있다.
식재료들을 각각 N / 2개씩 나누어 두 개의 요리를 하려고 한다. (N은 짝수이다.)
이때, 각각의 음식을 A음식, B음식이라고 하자.
비슷한 맛의 음식을 만들기 위해서는 A음식과 B음식의 맛의 차이가 최소가 되도록 재료를 배분해야 한다.
음식의 맛은 음식을 구성하는 식재료들의 조합에 따라 다르게 된다.
식재료 i는 식재료 j와 같이 요리하게 되면 궁합이 잘 맞아 시너지 Sij가 발생한다. (1 ≤ i ≤ N, 1 ≤ j ≤ N, i ≠ j)
각 음식의 맛은 음식을 구성하는 식재료들로부터 발생하는 시너지 Sij들의 합이다.
식재료 i를 식재료 j와 같이 요리하게 되면 발생하는 시너지 Sij의 정보가 주어지고, 가지고 있는 식재료를 이용해 A음식과 B음식을 만들 때, 두 음식 간의 맛의 차이가 최소가 되는 경우를 찾고 그 최솟값을 정답으로 출력하는 프로그램을 작성하라.
자세한 예시는 여기로.
제약 사항
시간 제한 : 최대 50개 테스트 케이스를 모두 통과하는 데 C / C++ / Java 모두 3초
식재료의 수 N은 4이상 16이하의 짝수이다. $(4 ≤ N ≤ 16)$
시너지 Sij는 1이상 20,000이하의 정수이다. $(1 ≤ Sij ≤ 20,000, i ≠ j)$
i와 j가 서로 같은 경우의 Sij값은 정의되지 않는다. 입력에서는 0으로 주어진다.
입력
입력의 맨 첫 줄에는 총 테스트 케이스의 개수 T가 주어지고,
그 다음 줄부터 T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 식재료의 수 N이 주어진다.
다음 N개의 줄에는 N * N개의 시너지 Sij값들이 주어진다. i와 j가 서로 같은 경우는 0으로 주어진다.
출력
테스트 케이스 개수만큼 T개의 줄에 각각의 테스트 케이스에 대한 답을 출력한다.
각 줄은 “#t”로 시작하고 공백을 하나 둔 다음 정답을 출력한다. (t 는 1부터 시작하는 테스트 케이스의 번호이다.)
정답은 두 음식 간의 맛의 차이가 최소가 되도록 A음식과 B음식을 만들었을 때 그 차이 값이다.
풀이
주어진 재료의 절반씩 사용하여 요리를 만들어 두 요리의 맛 차이가 최소로 되도록 하는 문제이다.
이 댸 재료의 절반을 사용하는 것을 다음과 같은 조합으로 나타낼 수 있다.
\[{N}\choose{N//2}\]두 요리에 대한 재료를 모두 구해야 하나? 하고 생각할 수 있지만, 한 요리의 재료가 결정되면 나머지 하나의 재료는 결정되기 때문에 굳이 구할 필요는 없다.
그래서 range(1, n)에 대해 n // 2 개의 원소를 가지는 조합을 구하도록 search_recipe를 작성하였다. 이후 전체 집합에 대해 차집합하여 반대쪽 조합을 구한다.
1
2
3
...
comb2 = list(index_set - set(comb))
...
구해진 조합으로 맛을 계산하고 차이의 최솟값을 구하면 된다.
1
2
3
4
5
6
7
...
for i_idx, (i1, i2) in enumerate(zip(comb, comb2)):
for j1, j2 in zip(comb[i_idx + 1:], comb2[i_idx + 1:]):
food1 += recipe[i1][j1] + recipe[j1][i1]
food2 += recipe[i2][j2] + recipe[j2][i2]
min_diff = min(min_diff, abs(food1 - food2))
...
만들어준 조합 배열의 맨 앞에 [0]을 붙여주는 이유는 주어진 재료의 번호가 1부터 시작하기 때문에 인덱스와 맞춰주기 위함이다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
test_case = int(input())
def search_recipe(index_list, n):
if n == 1 :
return [[i] for i in index_list]
result = []
for i in range(len(index_list) - 1):
for j in search_recipe(index_list[i+1:], n - 1):
result.append([index_list[i]] + j)
return result
for t in range(test_case):
n = int(input())
min_diff = float('inf')
recipe = [list(map(int, input().split())) for _ in range(n)]
index_set = set(range(n))
comb_list = [[0] + c for c in search_recipe(list(range(1, n)), n // 2 - 1)]
for comb in comb_list:
comb2 = list(index_set - set(comb))
food1, food2 = 0, 0
for i_idx, (i1, i2) in enumerate(zip(comb, comb2)):
for j1, j2 in zip(comb[i_idx + 1:], comb2[i_idx + 1:]):
food1 += recipe[i1][j1] + recipe[j1][i1]
food2 += recipe[i2][j2] + recipe[j2][i2]
min_diff = min(min_diff, abs(food1 - food2))
print(f"#{t + 1} {min_diff}")