[백준OJ] 1034번 램프

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

1034번: 램프

---

 

풀이

먼저, 우리가 바꿀 수 있는것은 열이다. 열을 k번 바꾼뒤 각 행들을 모두 검사해서 켜진 행들의 최댓값을 찾아야 한다.

 

행을 하나하나 차례대로 검사를 하며, k번을 스위치를 누름으로 해당행이 켜진다면, 해당 행과 같은 모양의 행은 모두 켜진다. 

예를들어

101

010

101

이 있고, k=1 이라고 해보자.

 

그럼 1번째 행을 보면 2번째 열의 스위치를 누르면 111로 모두 켜진다. k번 눌렀을때 행이 모두 켜지므로, 1번째 행과 같은 3번째 행도 모두 켜진다고 볼 수 있다. 따라서 2번째 열의 스위치를 1번 누르면, 2개의 행이 켜진다고 볼 수 있다.

 

2번째 행을 보면, 누를 수 있는 횟수는 1번인데, 켜야하는 열이 2개이다. 따라서 해당 행은 뭘 해도 안켜지는 행이므로 넘어간다.

 

3번째 행도 1번째 행과 마찬가지이다.

 

이때, k가 홀수개라면, 꺼져있는 전구의 개수또한 홀수개여야 한다.

 

위의 예시에서 만약 k가 2라고 한다면, 1번째 행에서 2번째 행의 스위치를 한번 누르면 다 켜지는데, 남은 한번을 사용한다면 그 열의 스위치는 다시 꺼지기 때문에, 남아있는 전구의 홀짝과 k의 홀짝이 같아야한다!

 

 

시간복잡도

O(NM)

 

반응형

 

코드

#include <iostream>
#include<string>
using namespace std;

string arr[51];
int ret=0;
int n,m,k;

int main() {
	cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    cin>>k;
    for(int i=0;i<n;i++){
        int z=0;
        for(int j=0;j<m;j++){
            if(arr[i][j]=='0') z++;
        }
        
        if(z<=k&&k%2==z%2){
            int cnt=0;
            for(int j=0;j<n;j++){
                if(arr[i]==arr[j]) cnt++;
            }
            ret=max(ret,cnt);
        }
    }
    cout<<ret<<"\n";
	return 0;
}