기타콘서트 ( 1497 번 )

1497번: 기타콘서트

 

---

🧠 알고리즘

• 브루트포스(Brute Force, 완전 탐색)

 

✔️ 동작 방식

• 각 기타마다 연주 가능한 곡들을 집합(set)으로 저장
• 가능한 모든 기타 조합을 탐색 (combinations 활용)
• 조합마다 합집합을 구해 연주 가능한 곡 개수를 계산
• 가장 많은 곡을 연주할 수 있는 경우를 찾고, 그때 필요한 최소 기타 개수를 반환

---

 

🧾 코드

import sys
from itertools import combinations

def _main(n, m):
    answer, count = -1, 0
    gita = []
    for _ in range(n):
        now_m = set()
        name, play_m = sys.stdin.readline().rstrip().split()
        for i in range(len(play_m)):
            if play_m[i] == 'Y':
                now_m.add(i)
        gita.append(now_m)

    for combi_num in range(1, n + 1):
        for combi in combinations(gita, combi_num):
            now_ava_m = set.union(*combi)
            if len(now_ava_m) > 0 and len(now_ava_m) > answer:
                answer = len(now_ava_m)
                count = combi_num
                
    if answer == - 1:
        return - 1
    else:
        return count

n, m = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, m))

---

 

⏱️ 시간 복잡도

# 각 조합을 콤비네이션 조합으로 탐색 ( 지수형 시간 복잡도 )
for combi_num in range(1, n + 1):
	for combi in combinations(gita, combi_num):
    
해당 알고리즘 시간 복잡도 : 지수형 시간 복잡도 ( O(2 ** n * n * m) )