[Boj_1497] 기타콘서트

📎 문제 링크

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

 

▸ 문제

강토는 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을 출력한다.

 

📍 문제 정보

• 🥈 문제 레벨 : 실버 1
• 🔔  문제 유형 : 수학, 브루트포스 알고리즘, 조합론, 비트마스킹, 백트래킹
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

처음 문제를 읽고, 연주할 수 있는 곡을 boolean형 배열을 만들어 체크하면서

N개의 기타로 만들 수 있는 조합을 모두 만들어 연주할 수 있는 곡을 체크하는 방식으로 해결하려 했다.

 

입력을 받던 도중 비트마스킹이 생각났고, 곡의 개수가 최대 50개이므로 Long형 비트마스킹을 사용하면 모든 곡을 표현할 수 있다고 생각했다.

 

예를 들어, 연주가 가능한 곡은 1, 불가능한 곡은 0으로 표현한다고 해보자

YYYNN : 11100

NNNYY : 00011
위의 연주 가능한 목록에 대해 2개의 기타를 사용한다면, OR 연산을 사용해서 아래와 같이 표현할 수 있다.

YYYNN (11100) | NNNYY (00011) = YYYYY (11111)

즉, 모든 곡을 연주할 수 있는 것을 확인할 수 있다.

 

기타의 연주 가능 목록을 비트 형태로 표현한 후,

• 현재 가리키는 기타를 사용한 경우
  • OR 연산을 통해 연주 가능한 곡을 업데이트한다.
  • bit | guitarBit[depth]
• 현재 가리키지 기타를 사용하지 않은 경우
  • 다음 기타를 탐색한다.

로 나누어 백트래킹을 진행했다.

 

위의 탐색을 진행할 때,

모든 기타를 확인했거나, 모든 곡을 칠 수 있지만 최솟값이 아닌 경우 더 이상 탐색을 진행해도 의미가 없으므로 종료한다.

 

또한, 문제에서 중복되는 기타는 없다고 했기 때문에 인덱스만으로 계산이 가능하다고 생각하여

기타의 이름은 따로 저장하지 않았다.

 

✔ 최종 코드

 메모리 : 11600KB
 시간 : 68ms

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[] guitarBit; // 각 기타가 연주할 수 있는 곡의 정보를 비트마스킹으로 표현
    static int max = 0; // 연주 가능한 최대 곡 개수
    static int ans = 987654321; // 필요한 기타의 최소 개수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken()); // 기타 개수
        m = Integer.parseInt(st.nextToken()); // 곡 개수

        guitarBit = new long[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            st.nextToken(); // 기타 이름
            char[] guitarArr = st.nextToken().toCharArray();
            for (int j = 0; j < m; j++) {
                if (guitarArr[j] == 'Y') { // 연주 가능 1, 불가능 0
                    guitarBit[i] |= (1L << j);
                }
            }
        }

        // 확인한 기타 개수, 현재 연주 가능한 곡 개수, 사용한 기타 개수
        back(0, 0L, 0);

        StringBuilder sb = new StringBuilder();
        if (ans == 0) { // 연주할 수 있는 곡 X
            sb.append(-1).append("\n");
        } else sb.append(ans).append("\n");

        System.out.println(sb.toString());
    }

    private static void back(int depth, long bit, int usingGuitar) {
        int bitCnt = Long.bitCount(bit); // 현재 연주 가능한 곡 개수
		
        // 현재 연주할 수 있는 곡은 같지만 사용한 기타 개수가 적을 때
        if (bitCnt == max && usingGuitar < ans) {
            // 최소 기타 개수 갱신
            ans = usingGuitar;
        }
		
        // 최대 곡 개수 보다 연주할 수 있는 곡이 더 많을 때
        if (max < bitCnt) {
            // 사용한 기타 개수, 연주 가능한 최대 곡 개수 갱신
            ans = usingGuitar;
            max = bitCnt;
        }

        // 모든 곡을 칠 수 있지만 최솟값이 아닌 경우, 모든 기타를 확인한 경우
        if (bitCnt == m || depth == n) {
            return;
        }

        // 현재 기타 사용
        back(depth+1, bit | guitarBit[depth], usingGuitar+1);
        // 사용 X
        back(depth+1, bit, usingGuitar);
    }
}

 

해결하는데 꽤 시간이 걸린 문제였지만,

오랜만에 백트래킹 문제를 풀면서 비트마스킹까지 다시 공부할 수 있는 문제였다 ! 🔥

북마크 해뒀다 다시 풀어봐야지 😜