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보다 선택된 기타가 많아서 더 진행해봤자 최적의 해를 찾을 수 없는 경우이다.
'문제풀이 > 백트래킹' 카테고리의 다른 글
[Python/파이썬] 백준 1248번 Guess (0) | 2025.02.22 |
---|---|
[Python/파이썬] 백준 1759번 암호 만들기 (0) | 2025.02.11 |
[Python/파이썬] 백준 6987번 월드컵 (0) | 2025.02.05 |
[Python/파이썬] 백준 7490번 0 만들기 (0) | 2024.06.23 |
[Python/파이썬] 백준 15270번 친구 팰린드롬 (0) | 2024.05.28 |