BOJ 1034 램프

문제

• 링크 - https://www.acmicpc.net/problem/1034

문제 분류

• 난이도 - 하
• 태그 - 탐색

문제 풀이

이 문제는 조금 관찰력이 필요한 문제다. 어떤 열의 램프 상태가 서로 다른 두 행은 동시에 켜져있을 수 없다. 즉, 서로 다른 두 행이 동시에 켜져있으려면 최소한 그 열의 램프 상태는 같아야 한다. 모든 열에 대해서 확장하면 어느 두 행이 동시에 켜져있으려면 그 두 행의 램프 상태는 동일해야 한다. 이러한 사실을 깨닫게되면 스위치를 K번 눌러서 어떤 행이 켜질 수 있는지 확인하고, 이와 램프 상태가 동일한 램프들의 수를 세어서 이 문제를 해결할 수 있다.

소스 코드

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

#include <iostream> #include <cstdio> #include <map> #include <algorithm> using namespace std;   typedef long long lint;   int main() {   int n, m, k;   scanf("%d%d", &n, &m);     map<lint, int> row;   for (int i = 0; i < n; i++) {     lint v = 0;     for (int j = m - 1; j >= 0; j--) {       lint b;       scanf("%1lld", &b);       v += (b << j);     }     row[v]++;   }   scanf("%d", &k);     int ans = 0;   for (auto& p : row) {     int zero = 0;     for (int i = 0; i < m; i++) {       if ((p.first & (1LL << i)) == 0) {         ++zero;       }     }     if (zero > k) continue;     if ((k - zero) % 2 == 0) {       ans = max(ans, p.second);     }   }   printf("%d", ans); }