[백준/Python, Java, JavaScript] 1497 기타콘서트

📌문제 탐색하기

• 새로운 기타들을 사야하는데, 어떤 기타는 특정한 곡들만 제대로 연주할 수 있음
• 최대한 많은 곡을 연주하려고 할 때 필요한 기타의 최소 개수 구하기

입력

• 기타 개수 N, 곡의 개수 M (1 ≤ N ≤ 10, 1 ≤ M ≤ 50)
• 둘째줄 부터 N개의 줄에 (기타 이름, 기타가 연주할 수 있는 곡 정보)가 1번 곡부터 차례대로 주어짐
  • Y는 연주할 수 있는 것, N은 없는 것
  • 기타 이름은 대문자로만 이루어짐 (2 ≤ 기타 이름 ≤ 50, 중복 없음)

출력

• 필요한 기타의 개수 출력
  • 연주할 수 있는 곡이 없다면 -1

 

풀이 방법 생각해보기

각 기타가 연주할 수 있는 곡 정보에 대해 Y는 1, N은 0으로 변환하여 비트마스킹을 사용하는 것을 생각해볼 수 있다. 기타 개수가 10개 이하 이므로 완전 탐색도 충분히 가능하다. 백트래킹을 통해 기타를 고를 수 있는 모든 경우의 수를 구하고, 해당 기타들이 연주할 수 있는 곡 정보에 대해 비트 OR( | ) 연산을 해서 가장 큰 값이 나오는 경우를 반환한다. 이 경우 시간복잡도는 최악의 경우 O(2¹⁰)이 된다.

 

📌코드 설계하기

1. max_count와 max_value를 0으로 초기화한다.
2. 백트래킹을 수행할 함수 backtracking(current_value, current_idx, current_count)를 정의한다.
   1. max_value와 current_value를 비교한다.
      1. 둘의 값이 같고 max_count보다 current_count가 더 작다면 max_count를 현재 값으로 갱신한다.
      2. current_value가 더 크다면, max_value와 max_count를 현재 값으로 갱신한다.
   2. current_idx가 N과 같다면 함수를 종료한다.
   3. backtracking(current_value | guitars[current_idx+1], current_idx+1, current_count+1)를 호출한다.
   4. backtracking(current_value, current_idx+1, current_count)를 호출한다.
3. 기타의 개수 N과 곡의 개수 M을 입력받는다.
4. 리스트 guitars를 생성한다.
5. 기타들의 정보 (name, vailable_songs)를 입력받아, vailable_songs에 대해 Y를 1, N을 0으로 바꾸고 10진수로 변환하여 guitars에 저장한다.
6. backtracking(0, -1, 0)을 호출한다.
7. 만약 max_value가 0이라면 -1을 출력하고, 아니라면 max_count를 출력한다.

 

📌정답 코드

Python

import sys
input = sys.stdin.readline

max_value = max_count = 0

def backtracking(current_value, current_idx, current_count):
    global max_value, max_count
    
    if current_value == max_value:
        max_count = min(max_count, current_count)
    if current_value > max_value:
        max_value, max_count = current_value, current_count
        
    if current_idx == N:
        return
        
    backtracking(current_value | guitars[current_idx], current_idx+1, current_count+1)
    backtracking(current_value, current_idx+1, current_count)
    

N, M = map(int, input().split())

guitars = [int(input().split()[1].replace('Y', '1').replace('N', '0'), 2) for _ in range(N)]

backtracking(0, 0, 0)

if max_value == 0:
    print(-1)
else:
    print(max_count)

Java

import java.io.*;
import java.util.*;

public class Main {
    public static int maxValue = 0;
    public static int maxCount = 0;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        int[] guitars = new int[N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            st.nextToken();
            
            String valiable_songs = st.nextToken().replace('Y', '1').replace('N', '0');
            guitars[i] = Integer.parseInt(valiable_songs, 2);
        }
        
        backtracking(guitars, 0, 0, 0, N);
            
        if (maxValue == 0) {
            System.out.println(-1);
        } else {
            System.out.println(maxCount);
        }
    }
    
    public static void backtracking(int[] guitars, int currentValue, int currentIdx, int currentCount, int N) {
        if (currentValue == maxValue) {
            maxCount = Math.min(currentCount, maxCount);
        }
        if (currentValue > maxValue) {
            maxCount = currentCount;
            maxValue = currentValue;
        }
        if (currentIdx == N) return;
        
        backtracking(guitars, currentValue | guitars[currentIdx], currentIdx+1, currentCount+1, N);
        backtracking(guitars, currentValue, currentIdx+1, currentCount, N);
    }
}

• 곡의 개수가 최대 50개가 될 수 있으므로, 최대 50비트의 정수를 저장해야 한다. int는 32비트 정수형이므로 64비트 정수형인 long 자료형을 사용해줬다.

JavaScript

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const [N, M] = input[0].split(" ").map(Number);;
const guitars = Array.from({length: N}, () => 0n);

for (let i = 0; i < N; i++) {
    const valiableSongs = input[i+1].split(" ")[1].replaceAll('Y', '1').replaceAll('N', '0');
    guitars[i] = BigInt('0b' + valiableSongs);
}

let maxValue = 0n;
let maxCount = 0;

const backtracking = (currentValue, currentIdx, currentCount) => {
    if (currentValue === maxValue) {
        maxCount = Math.min(maxCount, currentCount);
    }
    if (currentValue > maxValue) {
        maxValue = currentValue;
        maxCount = currentCount;
    }
    
    if (currentIdx === N) return;
    
    backtracking(currentValue | guitars[currentIdx], currentIdx+1, currentCount+1);
    backtracking(currentValue, currentIdx+1, currentCount);
    
}

backtracking(0n, 0, 0);

console.log((maxValue ? maxCount : -1))