BOJ 1034 램프

문제

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

문제 분류

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

문제 풀이

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

소스 코드

#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); }