[BOJ][C++] 백준 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을 출력한다.

 

풀이

입력을 조금 까다롭게 줘서 입력 받는 코드가 좀 긴 편이다

    cin >> n >> m;
    v.assign(n, vector<bool>(m));
    
    for(int i=0; i<n; i++) {
        string name, input;
        cin >> name >> input;
        
        for(int j=0; j<m; j++) {
            v[i][j] = input[j]=='Y';
        }
    }

 

이제 각 기타를 돌면서 포함 시키거나 포함 시키지 않는 경우를 다 살펴보면서

최대한 많은 곡을 연주할 수 있을 때 기타의 갯수를 return 하면 된다.

백트래킹이다.

 

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> ci;

int n,m;
vector<vector<bool>>v;
vector<ci>ans; // ans{a,b} = a개의 곡을 b개의 기타로 연주할 수 있다

int getSongNum(vector<bool>&song) {
    int num = 0;
    for(bool b : song) {
        num += b;
    }
    return num;
}

void recur(int k, vector<bool>song, int guitar) {
    // 모든 기타를 다 확인
    if(k>=n){
        int songNum = getSongNum(song);
        ans.push_back({songNum, guitar});
        return;
    }

    // k번 기타 선택 안함
    recur(k+1, song, guitar);
    
    // K번 기타 선택함
    for(int i=0; i<m; i++) {
        if(v[k][i]) {
            song[i] = true;
        }
    }
    recur(k+1, song, guitar+1);
}

bool cmp(ci a, ci b) {
    if(a.first == b.first) {
        return a.second < b.second;
    }
    return a.first > b.first;
}

int solution() {
    recur(0, vector<bool>(m,false), 0);

    // 곡의 수가 크고 기타의 수가 작은 순서대로 정렬
    sort(ans.begin(), ans.end(), cmp);

    if(ans[0].first == 0) {
        // 연주할 수 있는 곡이 없음
        return -1;
    }
    
    return ans[0].second;
}

int main() {
    // 입력
    cin >> n >> m;
    v.assign(n, vector<bool>(m));
    
    for(int i=0; i<n; i++) {
        string name, input;
        cin >> name >> input;
        
        for(int j=0; j<m; j++) {
            v[i][j] = input[j]=='Y';
        }
    }

    // 풀이 및 출력
    cout << solution();
    
    return 0;
}

 

 

 

시행착오

예제3을 주의하자.

모든 곡을 다 연주할 필요가 없다 (ㅋㅋ)

덕분에 열심히 짠 코드 던지고 새로 짬 ㅎ..ㅎ

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n,m;
vector<vector<bool>>v;
vector<int>ans;

// 공연이 가능한가 = 모든 노래를 연주할 수 있는가
bool isComplete(vector<bool>&song) {
    for(bool i : song) {
        if(!i) return false;
    }
    return true;
}

void recur(int k, vector<bool>song, int guitar) {
    if(isComplete(song)) { // 모든 노래 연주 가능
        ans.push_back(guitar);
        return;
    }
    
    if(k>=n){ // 모든 기타를 다 확인
        return;
    }

    // k번 기타 선택 안함
    recur(k+1, song, guitar);
    
    // K번 기타 선택함
    for(int i=0; i<m; i++) {
        if(v[k][i]) {
            song[i] = true;
        }
    }
    recur(k+1, song, guitar+1);
}

int solution() {
    recur(0, vector<bool>(m,false), 0);
    
    if(ans.size() == 0) {
        return -1;
    }
    
    sort(ans.begin(), ans.end());
    return ans[0];
}

int main() {
    // 입력
    cin >> n >> m;
    v.assign(n, vector<bool>(m));
    
    for(int i=0; i<n; i++) {
        string name, input;
        cin >> name >> input;
        
        for(int j=0; j<m; j++) {
            v[i][j] = input[j]=='Y';
        }
    }

    // 풀이 및 출력
    cout << solution();
    
    return 0;
}