[SWEA] 4012. [シミュレーションソフトウェア能力テスト]シェフ

📚 質問する

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeUtVakTMDFAVH&categoryId=AWIeUtVakTMDFAVH&categoryType=CODE&problemTitle=4012&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1
自分の好きな食べ物を選ぶので、組み合わせです.
食べ物を選ぶ場合を考えてみましょう.だから組み合わせです.

食材が4種類ある場合は以下の通りです.
0 0 1 1
0 1 1 0
0 1 0 1
1 0 0 1
1 0 1 0
1 1 0 0
このとき0 0 1 1と1 1 0 0は同じである.そのため、半分以上の価格は除去されます.
このため、左端または右端または片側が0のみであることが確認できます.
最後に引いた回数を除いて、その時は0万として半分しか確認しませんでした.
組み合わせを選んで、当時の食べ物を訪問中に入れます.
以上のように,半分を選ぶ関数を実現し,味の違いを求める値引関数を構築する.
与えられた食物の2次元配列では,2つのドアを回し,配列にアクセスすることによってiとjの両方が選択されたかどうかを確認した.
どちらも0のときと1のときを合わせて減らすので、1つの変数を宣言し、両方を選んだら加算し、どちらも選ばなければ削除します.
この倹約値がglobalと宣言された値より小さい場合、更新されます.

📒 コード#コード#

def taste():    # 맛 차이의 절댓값
    global min_result
    result = 0
    for i in range(n):
        for j in range(n):
            if visited[i] and visited[j]:   # 고른 걸 더해주고
                result += arr[i][j]
            elif visited[i] == 0 and visited[j] == 0:   # 안 고른 걸 빼준다.
                result -= arr[i][j]
    min_result = min(min_result, abs(result))   # 최솟값으로 초기화
    return


def recur(cur, num):
    if num > n // 2:        # 절반을 넘게 고르는 경우는 종료
        return
                            # 0011 1100처럼 대칭되면 같으므로 가장 큰 자릿수가 0일 때만 뽑는다.
    if cur == n - 1:        # 절반을 고르면 taste()를 돌고 종료, 아니면 그냥 종료
        if num == n // 2:   # 절반을 고르는 경우만
            taste()
        return

    recur(cur + 1, num)     # 선택하지 않는 경우

    visited[cur] = 1
    recur(cur + 1, num + 1)     # 선택하는 경우
    visited[cur] = 0


t = int(input())
for tc in range(1, 1 + t):
    n = int(input())
    arr = [list(map(int, input().split())) for _ in range(n)]
    visited = [0 for _ in range(n)]
    min_result = 10000000
    recur(0, 0)
    print(f'#{tc} {min_result}')

🔍 結果