백준 1497번: 기타콘서트 (JAVA)

문제

 

강토는 Day Of Mourning의 기타리스트로, 다가오는 공연을 준비하고 있다.

어느 날 강토의 집에 도둑이 들어서 기타를 모두 도둑맞고 말았다. 기타를 사야 한다.

강토는 공연 때 연주할 노래의 목록을 뽑아 놓았다. 하지만, 하나의 기타로 모든 곡을 연주할 수는 없다. 어떤 기타는 어떤 곡을 연주할 때, 이상한 소리가 나기 때문이다. 항상 완벽을 추구하는 강토는 이런 일을 용납하지 않는다.

최대한 많은 곡을 제대로 연주하려고 할 때, 필요한 기타의 최소 개수를 구하는 프로그램을 작성하시오.

예를 들어, GIBSON으로 1, 2, 3번 곡을 제대로 연주할 수 있고, FENDER로 1, 2, 5번 곡을 제대로 연주할 수 있고, EPIPHONE으로 4, 5번 곡을 제대로 연주할 수 있고, ESP로 1번곡을 제대로 연주할 수 있다면, 세준이는 EPIPHONE과 GIBSON을 사면 최소의 개수로 모든 곡을 연주할 수 있다. 

입력

첫째 줄에 기타의 개수 N과 곡의 개수 M이 주어진다. N은 10보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 기타의 이름과 기타가 연주할 수 있는 곡의 정보가 1번 곡부터 차례대로 주어진다. Y는 연주할 수 있는 것이고, N은 없는 것이다. 기타의 이름은 알파벳 대문자로만 이루어져 있고, 길이는 2 이상, 50 이하이다. 두 기타의 이름이 같은 경우는 없다.

출력

첫째 줄에 필요한 기타의 개수를 출력한다. 만약 연주할 수 있는 곡이 없으면 -1을 출력한다.

 

---

 

풀이

완전탐색 문제의 일환으로 접하게 된 문제이다. Python이면 신나게 문자열 처리 했을 거 같은데, JAVA에서 문자열/리스트 조작이 익숙하지 않다보니 비트마스킹으로 풀게 되었다(그리고 비트마스킹으로 푸는게 간결한 듯하다.).

 

1. input 처리

• 주어진 input값 중 기타의 이름은 필요없는 정보이므로 버린다. 
• 기타가 연주할 수 있는 값이 Y와 N으로 구성된 String으로 제시되는데, Y를 1, N을 0으로하는 2진수로 변환하여 '연주할 수 있는 곡들'을 canPlay의 index에 저장한다(0번째 기타는 0번째 index에, 1번째 기타는 1번째 index에, ...).

 

2. 풀이 아이디어

• 최대로 연주할 수 있는 곡의 수, 이 때의 최소 기타 개수를 각각 canPlayMax랑 minGuitarNum이라고 하자.
• 기타의 개수 N에 대하여 부분집합을 완전탐색한다. 기타 개수가 작은 순서부터 탐색하면(코드의 R에 대한 for문) 코드 구현이 깔끔해진다.
• 각 부분집합에 대하여, 각 기타가 연주할 수 있는 노래의 합을 bitwise or("|") 연산으로 구한다. 이를 canPlaySum이라는 long 변수에 저장한다.
• canPlaySum의 1의 개수를 세준다(코드 내 'countOne' 함수). 이를 canPlayMax랑 비교하여, 만약 Max값보다 크다면 Max값을 굧체해주고 minGuitarNum도 현재 기타의 개수로 교체해준다(기타 개수가 적은 부분집합부터 살펴보기에 비교 필요 없음.).

 

 

배운 점

JAVA에서는 언제나 숫자의 범위에 대해 신경써야한다. canPlay의 원소, canPlaySum은 최대 2**50 - 1 까지 값이 가능하므로 long타입으로 저장해야하는데, int로 저장하는 바람에 30분은 날린 듯하다. 맞왜틀...맞왜틀...만 계속 머리 속에서 맴돌았다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, M;
	static long[] canPlay;
	static int minGuitarNum = -1;
	static int canPlayMax = 0;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		canPlay = new long[N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			st.nextToken();
			long temp = 0;
			String canPlayString = st.nextToken();
			for (int j = 0; j < M; j++) {
				temp *= 2;
				if (canPlayString.charAt(j) == 'Y') {
					temp++;
				}
			}
			canPlay[i] = temp;
		}
		
		for (int R = 1; R <= N; R++) {
			minGuitar(0, 0, R, 0);
			if (canPlayMax == M) break;
		}
		System.out.println(minGuitarNum);
		for (int i = 1; i < 32; i++) {
		}
	}

	
	public static void minGuitar(int cnt, int start, int R, long canPlaySum) {
		if (cnt == R) {
			int canPlayNum = countOne(canPlaySum);
			if (canPlayNum > canPlayMax) {
				canPlayMax = canPlayNum;
				minGuitarNum = R;
			}
			return;
		}
		
		for (int i = start; i < N; i++) {
			minGuitar(cnt+1, i+1, R, canPlaySum|canPlay[i]);
		}
	}

	
	public static int countOne(long canPlaySum) {
		int cnt = 0;
		while (canPlaySum > 0) {
			if (canPlaySum % 2 == 1) cnt++;
			canPlaySum /= 2;
		}
		return cnt;
	}
}