[C++] 백준 BOJ 1034번 램프

어떤 행이 반드시 켜져야한다고 생각하자. 

그렇다면 그 행을 키는 방법은 단 한가지 밖에 존재하지 않는다고 생각할 수 있다. 

만일 불이 꺼져있다면 스위치를 누르면 되고, 불이 켜져있다면 스위치를 건드리지 않으면 된다. 

(하나의 스위치를 두번 누르는 것은 결국 스위치를 조작하지 않은 것과 같다는 것을 생각하자) 

 

 

모든 행을 돌아보면서 돌아보는 행이 모두 켜져있다고 가정을 하게 되면 모든 열에 대해 스위치를 누르는 방법이 결정된다. 

그걸 이용하면 브루트포스 방식을 이용하여 문제를 풀수있다. 

#include <iostream>
#include <cstring>
using namespace std;
int change[51];
int numbers[52][52];
int N, M, K, ans;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //입력 받기
    cin>>N>>M;
    for(int i=0;i<N;i++){
        cin.ignore();
        for(int j=0;j<M;j++){
            char num=cin.get();
            numbers[i][j]=num-'0';
        }
    }
    cin>>K;
    
    for(int i=0;i<N;i++){
        //i번째 행을 모두 1로 고정 (i번째 행이 켜져있다고 가정) => 스위치는 누르는 방법이 결정됨
        int changed=0;
        memset(change, 0, sizeof(change));
        for(int j=0;j<M;j++){
            if(numbers[i][j]==0){
                change[j]=1;
                changed+=1;
            }
        }
        int lamp=0;
        for(int j=0;j<N;j++){
            //j번째 행이 켜져있는가
            bool isOn=true;
            for(int k=0;k<M;k++){
                if((change[k]==0 && numbers[j][k]==1) || (change[k]==1 && numbers[j][k]==0))
                    continue;
                else{
                    isOn=false;
                    break;
                }
            }
            if(isOn)
                lamp+=1;
        }
        numbers[i][M]=lamp;
        numbers[i][M+1]=changed;
    }
    
    for(int i=0;i<N;i++){
        if((K-numbers[i][M+1])%2==0 && ans<numbers[i][M] && numbers[i][M+1]<=K)
            ans=numbers[i][M];
    }
    cout<<ans;
    return 0;
}

change 배열에 어떤 열의 스위치를 누르는지 여부를 저장

numbers[i][M]에 그 결과 최대 몇 개의 행이 켜졌는가 저장

numbers[i][M+1]에 총 스위치를 몇 번 누르는가 저장 (한 스위치는 최대 한번만 누른다고 생각했을 때)

 

단, 여기서 만들 수 있는 최대값이 무조건 답이 되는 것이 아니다.

한 스위치를 두번 누른 것이 아무것도 하지 않은 것과 같은 상태라는 것을 생각해보면 주어진 K와 numbers[i][M+1]의 차이가 2의 배수 만큼 차이가 나야한다. 

답을 구하다가 총 스위치를 누른 횟수가 K보다 커지는 경우가 있었다... 이것 또한 걸러주어야한다. 

총 시간복잡도 $$O(N^2M)$$으로 해결

(사실 N과 M이 50보다 작다는 것에서 브루트포스라는걸 살짝 눈치챌 수 있다.)