Create 1497.cpp

encrypted-def · web-flow · commit 5b2480cd2830 · 2024-03-17T21:39:47.000+09:00
diff --git a/Appendix C/1497.cpp b/Appendix C/1497.cpp
@@ -0,0 +1,46 @@
+// http://boj.kr/2532d97629b04d7c86f15db6bee08772
+#include <bits/stdc++.h>
+using namespace std;
+
+int n, m;
+long long state[10];
+
+int bit_cnt(long long x){
+  int ret = 0;
+  for(int i = 0; i < m; i++){
+    ret += (x >> i) & 1;
+  }
+  return ret;
+}
+
+int main(){
+  ios::sync_with_stdio(0);
+  cin.tie(0);
+  
+  cin >> n >> m;
+  for(int i = 0; i < n; i++){
+    string name, tmp; // name은 사실 의미없음
+    cin >> name >> tmp;
+    for(int j = m-1; j >= 0; j--){
+      state[i] = (state[i] << 1) | (tmp[j] == 'Y');
+    }
+  }
+
+  pair<int, int> ans = {0, -1}; // {연주할 수 있는 곡의 수, 필요한 기타의 수}
+  for(int tmp = 0; tmp < (1 << n); tmp++){
+    long long comb = 0; // 조합한 결과
+    for(int i = 0; i < m; i++){
+      if((tmp & (1LL << i)) == 0)
+        continue;
+      comb |= state[i];
+    }
+    int song_num = bit_cnt(comb);
+    int guitar_num = bit_cnt(tmp);
+    if(ans.first < song_num) // 1. 연주할 수 있는 곡의 수가 더 많을 경우
+      ans = {song_num, guitar_num};
+    // 2. 연주할 수 있는 곡의 수는 같은데 필요한 기타의 수가 더 적을 경우
+    else if(ans.first == song_num && ans.second > guitar_num)
+      ans = {song_num, guitar_num};
+  }
+  cout << ans.second << '\n';
+}
