[Python/파이썬] 백준 1497번 기타콘서트

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

코드

n, m = map(int, input().split())

guitars = []
maximum_song = 0
for _ in range(n):
    name, songs = input().split()
    binary = ""
    for song in songs:
        binary += "1" if song == "Y" else "0"
    guitars.append((name, int(binary, 2)))
    maximum_song |= int(binary, 2)

answer = int(1e9)


def bt(idx, guitar_cnt, song):
    global answer
    if idx == n or guitar_cnt > answer:
        return
    if song | guitars[idx][1] == maximum_song:
        answer = min(answer, guitar_cnt+1)
        return
    # 기타 포함
    bt(idx+1, guitar_cnt+1, song | guitars[idx][1])
    # 기타 포함 X
    bt(idx+1, guitar_cnt, song)


bt(0, 0, 0)
print(answer if maximum_song != 0 else -1)

 

곡의 연주 가능 여부를 1/0으로 바꾸면 비트마스킹을 사용하여 쉽게 할 수 있다.

 

1. 최대한 많은 곡을 연주하는 경우는 모든 기타의 연주 가능한 노래들을 OR 연산해주면 된다. 이렇게 구한 값을 maximum_song이라는 변수에 저장해둔다.

2. 0-1 KANPSACK처럼 현재 기타를 넣을지 말지 결정한다. 이 과정은 백트래킹 알고리즘을 사용하여 재귀적으로 진행된다. 가지치기는 모든 기타를 돌아보거나(idx == n) 현재의 answer보다 선택된 기타가 많아서 더 진행해봤자 최적의 해를 찾을 수 없는 경우이다.