[BOJ/C++] 1034 - 램프

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

---

 

해당 문제는 흔한 브루트포스 문제랑은 살짝 결이 다른 느낌을 받았습니다.

 

처음 생각했던 풀이는 2^m가지 경우를 다 돌리는 풀이였습니다.

하지만, 스위치를 누르는 횟수 k에 대해서 m<k인 경우에 대해서도 생각할 필요가 있었습니다. 

 

한 스위치를 두번 누르는 것은 안누른 것과 동치이기 때문에 이런 경우에 대해서 따로 예외처리를 해주려고 했으나, 생각해주어야 할 것들이 너무 많아지더라구요. 결국 기존 풀이는 폐기하고, 다른 풀이를 생각해보았습니다.

 

관찰한 내용은 아래와 같습니다. 

1. 만약 두 개의 행 A,B가 동일한 형태를 띈다면, A행이 켜진다면 반드시 B형도 켜질 것입니다. 반대로, A,B가 하나라도 다른 부분이 있다면, 해당 행은 반드시 동시에 켜질 수 없습니다. 

2. 한 행에서 켜야 하는 램프의 수 x가 스위치를 누르는 횟수 k보다 작거나 같은 경우에는 무슨일이 있어도 해당 행을 킬 수 없습니다.

3. x<k일 때, 한 행에서 켜야 하는 램프의 수 x와 스위치를 누르는 횟수 k의 패리티가 동일해야만 해당 향을 킬 수 있습니다. 

 

3번 규칙에 대해서 생각해보면,

예를 들어 한 행에 꺼져있는 램프가 2개이고 스위치를 누르는 횟수가 3회 인 경우에는, 램프 2개를 끈 이후에 스위치를 반드시 한 번 더 눌러야 하므로 최종적으로 램프가 하나가 꺼져있을 것입니다. 

꺼져있는 램프가 2개이고 스위치를 누르는 횟수가 4회인 경우에는, 램프 2개를 끈 이후에 스위치를 2번 더 눌러야하는데, 한 스위치를 두번 누르는 것은 램프 상태에 영향을 끼치지 않으므로 해당 행은 켤 수 있는 행이 됩니다. 

 

위의 관찰을 기반으로 풀이를 다시 작성하면, 

임의의 한 행을 잡고, 스위치를 k번 눌러서 해당 행을 킬 수 있는 지 확인합니다.

켤 수 있다면, 해당 행과 동일한 다른 행도 켤 수 있음이 자명하므로, 이를 기록합니다.

 

모든 행을 위처럼 확인한 후에 최종적으로 정답을 출력했습니다. 

---

코드

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(int i=x;i<y;i++)
#define REP(i,x,y) for(int i=x;i<=y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
typedef tuple<int,int,int> ti3;
int dx[] = {-1,0,1,0};
int dy[] = {0,1,0,-1};
/*----------------------*/

const int MX = 50;
string board[MX+1];
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m; cin>>n>>m;
    rep(i,0,n) cin>>board[i];
    int k; cin>>k;

    map<string,int> ma;

    rep(i,0,n){
        int cnt = 0;
        rep(j,0,m) cnt+=(board[i][j]=='0');

        if(cnt>k || (cnt%2!=k%2)) continue;

        ma[board[i]]++;
    }

    int ans = 0;
    for(auto[a,b]: ma){
        ans = max(ans, b);
    }
    cout<<ans<<'\n';
}