문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH
요약: A음식과 B음식의 맛의 차이가 최소가 되도록 재료를 배분, 맛의 차이 최소값 구하기
- 재료 고르기 (조합)
우선 음식 재료를 정하기 위해 N개의 재료 중 N/2개의 재료를 고르기 위한 알고리즘이 필요하다.
생각해보면 음식의 순서는 상관 없기 때문에 조합(combination)을 사용해야한다.
iterationtools를 사용하면 간단하지만, 아무래도 이런 라이브러리는 활용할 수 없을 수도 있기 때문에 직접 조합을 생성하는 코드를 작성해 보았다.
def select(info, selected, N, r, idx, next):
global min_val
# 선택을 다 했으면
if idx == r:
nums = selected[:r]
val = score(info, nums, N)
min_val = min(min_val, val)
return
if next >= N: return
selected[idx] = next
# 현재 재료(next) 선택
select(info, selected, N, r, idx + 1, next + 1)
# 현재 재료(next) 값 미선택
select(info, selected, N, r, idx, next + 1)- info: 음식 시너지 정보가 담긴 배열
- selected: 선택된 음식
- N: 총 음식 재료 개수
- r: 선택해야할 음식 재료 개수
- idx: 고를 음식 순번
- next: 음식 재료 번호
위와 같은 파라미터들을 활용한다.
재귀를 이용해서 하나씩 선택을 해나아가는 알고리즘이다.
if idx == r 부분은 r개를 모두 선택했을 때, 이후 프로세스를 처리한다.
만약 아직 r개를 다 고르지 못했다면, 다음으로 넘어온다.
그리고 next가 재료의 번호 이기 때문에 N을 넘으면 더 이상 진행하지 않는다.
모든 종료조건을 통과했으면,
selected[idx] = next 즉, 고를 순번(idx)에 음식 재료 번호(next)를 할당한다.
그리고 이 선택을 유지할려면 다음 순번을 고르기 위해 idx + 1, next + 1를 해주고,
해당 재료를 선택하지 않는다면 고르는 순번 증가 없이 재료만 다음 재료로 설정해준다.
그러면 자연스럽게 selected[idx] = next + 1이 되면서 해당 순번에 다음 재료가 선택이된다.
다시 돌아와서 r개를 모두 선택했을 때, 골라진 r개를 이용해 각 음식의 점수를 계산한다.
선택된 재료들(A의 음식재료)과 선택되지 못한 재료들(B의 음식재료)을 나누고,
반복문을 활용해 각 음식의 점수를 계산해준다.
두 음식 점수 차이에 절대값을 적용해 반환해준다.
def score(info, selected, N):
A = 0
B = 0
not_selected = [i for i in range(N) if i not in selected]
for i in range(N):
if i in selected:
for j in selected:
A += info[i][j]
else:
for j in not_selected:
B += info[i][j]
# print(f'A: {selected}, B: {not_selected}')
# print(f'A: {A}, B: {B}')
return abs(A-B)점수 계산 후 해당 조합에서 min_val = min(min_val, val)을 이용해, global한 최소값을 업데이트 해준다.
즉, 모든 조합에 대해 점수를 계산해보고, 최소값을 업데이트 하게됨으로 두 음식의 점수 차이의 최소값을 구할 수 있게 된다.
전체코드
def score(info, selected, N):
A = 0
B = 0
not_selected = [i for i in range(N) if i not in selected]
for i in range(N):
if i in selected:
for j in selected:
A += info[i][j]
else:
for j in not_selected:
B += info[i][j]
# print(f'A: {selected}, B: {not_selected}')
# print(f'A: {A}, B: {B}')
return abs(A-B)
def select(info, selected, N, r, idx, next):
global min_val
# 선택을 다 했으면
if idx == r:
nums = selected[:r]
val = score(info, nums, N)
min_val = min(min_val, val)
return
if next >= N: return
selected[idx] = next
# 현재 재료(next) 선택
select(info, selected, N, r, idx + 1, next + 1)
# 현재 재료(next) 값 미선택
select(info, selected, N, r, idx, next + 1)
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
# 재료개수 입력
N = int(input())
# 시너지 정보 입력
info = [list(map(int, input().split())) for _ in range(N)]
min_val = 999999999
selected = [0] * N
select(info, selected, N, N//2, 0, 0)
print(f'#{test_case} {min_val}')