[BOJ/백준][Gold5] 1034 : 램프 (C++)

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

1034번: 램프

 

 

[난이도] Gold5
[유형] 구현

[풀이]
어떤 행 i,j가 K번 스위치를 눌렀을 때 두 행 모두 켜져있는 상태가 되려면
i,j 행은 초기 상태가 같아야 합니다.
왜냐하면 어떤 열 m의 초기 상태가 달라 lamp[i][m] != lamp[j][m] 상태인 경우
m번 열의 스위치를 아무리 눌러도 lamp[i][m]과 lamp[j][m] 는 동시에 바뀌기 때문에
계속 lamp[i][m] != lamp[j][m] 상태일 수밖에 없습니다.

그러므로 K번 스위치를 눌러서 켜진 상태(모든 열이 1인 상태)를 만들 수 있는
행 i에 대해서 i행과 같은 초기상태를 가지는 행 j의 개수를 구해주면 됩니다.
이 값을 모든 i에 대해 구해주면서 최댓값을 업데이트 해주면서 나온 최종 값이 정답이 됩니다.

K번 스위치를 눌러서 켜진 상태를 만들 수 있는지는
0의 개수가 K보다 작으면서, 0의 개수를 2로 나눈 나머지와 K를 2로 나눈 나머지가 같아야 합니다.

 

 

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N,M,K,ans;
string lamp[50];
int main(){
    cin >> N >> M;
    for(int i=0;i<N;i++) cin >> lamp[i];
    cin >> K;
    for(int i=0;i<N;i++){
        auto s = lamp[i];
        int cnt=0;
        for(int j=0;j<M;j++) if(s[j]=='0') cnt++;
        if(cnt > K || cnt%2 != K%2) continue;
        int sameCnt=0;
        for(int j=0;j<N;j++) if(s==lamp[j]) sameCnt++; 
        ans=max(ans,sameCnt);
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1034.cpp