BOJ 1034 - 램프

www.acmicpc.net/problem/1034

1034번: 램프

 

행 전체의 전구가 켜져있으면, 그 행을 켜져있다고 부른다.

그래서 어떤 행을 키려면 그 행에서 꺼져있는 열들을 전부 켜줘야 그 행을 켜져있는 행으로 바꿀 수 있다.

만약 처음 입력 받은 값에서 서로 다른 두 행, i, j 가 다른 값들을 갖고 있다면, 둘은 동시에 켜질 수 없을 것이다.

예를들면, 예제입력 1에서

01

10

10 이 주어질때,

첫번째행 01 과 두번째행 10 은 처음 입력이 다르고, 둘다 동시에 켜져있는 행으로 만들 수는 없다.

 

 

어떤 행을 켜져 있는 행으로 바꿀 수 있는지 없는지 판별하기 위해서는 

스위치를 누르는 횟수인 k 값과 비교를 해야 판별할 수 있는데

첫번째로, 해당 행에 꺼져있는 전구(0)의 갯수 가 k 개 이하일때 가능하고

두번째로, 해당 행에 꺼져있는 전구(0)의 갯수를 2로 나눈 나머지와 k를 2로 나눈 나머지 값과 동일해야 한다.

(스위치를 짝수번 누르면, 결국 처음이랑 똑같은 결과가 되기 때문)

 

문제에서 구하는 것은 켜져있는 행의 최대 갯수이므로, k번 눌러서 켜져있는 행으로 바꿀 수 있는 행 중에서(위의 두 조건을 만족하는) 동일한 행의 최대 갯수를 찾아내면된다.

 

 

- c++

#include <algorithm>
#include <iostream>
#include <string>
 
#define MAX 51
 
using namespace std;
 
int n, m, k, answer;
string adj[MAX];
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
 
    cin >> n >> m;
    
    for (int i = 0; i < n; ++i) {
        cin >> adj[i];
    }
    
    cin >> k;
    
    for (int i = 0; i < n; ++i) {
        int zero_num = 0, same_row = 0;
        for (int j = 0; j < m; ++j) {
            if (adj[i][j] == '0')
                zero_num++;
        }
        
        if (zero_num > k || zero_num % 2 != k % 2) continue;
        
        for (int j = 0; j < n; ++j) {
            if (adj[i] == adj[j]) 
                same_row++;
        }
        
        answer = max(answer, same_row);
    }    
    
    cout << answer;
    return 0;
}