[Python] 30959번 앙상블할래?

https://www.acmicpc.net/problem/30959

---

 

24/05/14

 

 

간단한 브루트포스 문제다. 파이썬은 이러한 문제에 있어서 쉽게 구현을 할 수 있어서 좋은 것 같다.

---

 

문제 접근 방식:

 

 

$N$의 제한이 $16$까지이고, 항상 홀수 개의 모델만 선택한다고 했으므로 전수조사를 해도 충분히 시간안에 들어올 수 있음을 생각할 수 있다.

 

하나의 조합을 통해 앙상블을 구성하는 것은 조합의 크기와 예측 항목의 개수를 곱한 크기에 비례함을 확인할 수 있다.

 

그 수가 그렇게 많지 않으므로, 모든 조합을 확인해보면 된다.

 

파이썬의 itertools 모듈의 combinations함수를 사용하면 n개 중 r개를 선택하는 모든 조합의 경우들을 확인할 수 있으므로, 이를 사용하여 쉽게 구현할 수 있다.

 

인덱스에 조심해서 구현해야 함에 유의하자.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 30959번 앙상블할래?
# 브루트포스
'''
접근 방법:
브루트포스
'''
import sys
input = sys.stdin.readline
from itertools import combinations

def solve():
    N, M = map(int, input().split())
    ANS = list(map(int, input().split()))
    models = [list(map(int, input().split())) for _ in range(N)]
    MAX_CORRECT = max(sum((1-model[i]^ANS[i]) for i in range(M)) for model in models)
    for choose in range(1, N+1, 2):
        for tpl in combinations(range(N), choose):
            ansenble = [0 for _ in range(M)]
            for i in range(M):
                ZO = [0, 0]
                for j in tpl:
                    ZO[models[j][i]] += 1
                if ZO[0] < ZO[1]:
                    ansenble[i] = 1
            if MAX_CORRECT < sum((1-ANS[i]^ansenble[i]) for i in range(M)):
                print(1)
                return
    print(0)
    return
solve()