[BOJ_1497] 기타콘서트(python)

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

문제

---

코드

from itertools import combinations

target = 0
t = []
n, m = map(int, input().split())
for _ in range(n):
    name, song = input().strip().split()
    r = 0
    for i in range(m):
        if song[i] == 'Y':
            r |= (1 << i)
    target |= r
    if r:
        t.append(r)

ans = 0
for i in range(1, n+1):
    for j in list(combinations(t, i)):
        base = 0
        for k in j:
            base |= k
        if target == base:
            ans = len(j)
            break
    if ans: break

print(ans if ans else -1)

---

Idea 1

r |= (1 << i) : 비트마스킹 OR연산을 통해 연주 할 수 있는 곡 결합
target |= r : 각각의 곡을 OR연산을 통해 전체 곡을 담는 변수 생성

combinations(t, i) : 곡들로 만들 수 있는 모든 경우의 수 
base |= k : 경우의 수 마다 OR연산을 통해 연주 할 수 있는 곡 결합