[백준 1034] 램프

작성일 | In |

문제 링크

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

풀이

하나의 행이 켜지기 위해 눌러야 하는 스위치의 목록은 유일합니다. 반대로 생각해보면 누르는 스위치의 목록이 주어졌을 때 행이 켜지기 위한 행의 상태 또한 유일하다는 것을 알 수 있습니다. 그러므로 상태가 같은 행끼리 묶고 스위치를 $K$번 눌러 그 행을 킬 수 있다면 정답을 묶어진 행의 개수로 갱신해주면 됩니다. 스위치를 눌러야 하는 횟수 $c$는 행에서 $0$의 개수로 구할 수 있고 스위치를 짝수번 누른다면 원 상태로 돌아온다는 특징을 이용해 $c < K$여도 $c\%2 == K\%2$라면 스위치를 $K$번 눌러 그 행을 킬 수 있습니다. map에 길이가 $M$인 string을 $N$번 추가하는 것이 가장 큰 시간복잡도를 차지하므로 시간복잡도는 $O(NM \log N)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m, k, mx;
string s;
map<string, int> mp;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m;
    for(int i=0;i<n;i++) cin >> s, mp[s]++;
    cin >> k;

    for(auto [s, x] : mp){
        int c = 0;
        for(int i=0;i<m;i++) if(s[i] == '0') c++;
        if(c <= k && c % 2 == k % 2) mx = max(mx, x);
    }
    cout << mx;
}