백준 1034 램프 c++ (완전탐색)

문제 출처 : https://www.acmicpc.net/problem/1034

1034번: 램프

문제

지민이는 각 칸마다 (1*1크기의 정사각형) 램프가 들어있는 직사각형 모양의 탁자를 샀다. 모든 램프는 켜져있거나 꺼져있다. 각 열의 아래에는 스위치가 하나씩 달려있는데, 이 스위치를 누를 때마다 그 열에 있는 램프의 상태가 바뀐다. (켜져있는 램프는 꺼지고, 꺼져있는 램프는 켜진다)

만약 어떤 행에 있는 램프가 모두 켜져있을 때, 그 행이 켜져있다고 말한다. 지민이는 스위치를 K번 누를 것이다. 서로다른 스위치 K개를 누르지 않아도 된다. 지민이는 스위치를 K번 눌러서 켜져있는 행을 최대로 하려고 한다.

지민이의 탁자에 있는 램프의 상태와 K가 주어졌을 때, 스위치를 K번 누른 후에 켜져있는 행의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져있는 상태이다. 마지막 줄에는 K가 주어진다. K는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 문제의 정답을 출력한다.

알고리즘 분류

• 브루트포스 알고리즘

풀이

열 단위로 램프를 껐다 켰다 하기 때문에, 1행과 2행의 패턴이 같다면 1행과 2행은 같이 켜졌다 꺼진다.

ex)

1행 : 010

2행 : 010

3행 : 110

 

1열과 3열 스위치를 누르면

1행 : 111

2행 : 111

3행 : 011

즉, 각각의 패턴에 대해 행의 불을 켤 수 있는지 검사하고, 불을 켤 수 있다면 해당 패턴이 몇 번 나오는지 검사한다.

불을 켤 수 있는 패턴이 가장 많이 나오는 횟수가 답이다.

불을 켤 수 있는지에 대한 검사는

패턴이 1010 일 때 0은 2개 있다.

이 패턴의 불을 켜려먼 일단 스위치를 짝수 번 누를 수 있어야 하고, 0의 개수인 2보다 여러 번 누를 수 있어야 한다.

패턴이 1000 일 때 0은 3개 있다.

이 패턴의 불을 켜려면 스위치를 홀수 번 누를 수 있어야 하고, 0의 개수인 3보다 여러 번 누를 수 있어야 한다.

즉 0의 개수를 cnt라고 할 때,

cnt<=k && cnt%2 == k%2를 만족해야 한다.

 

본인은 패턴의 수를 저장하기 위해 map을 사용했지만, 그냥 패턴들을 vector에 저장하고 첫 번째 패턴부터 같은 패턴이 몇 개 있는지 검사해도 된다.

코드

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

int n, m, k, answer = 0;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//k는 0<=k <=1000
	//n과 m은 1<= nm <=50
	cin >> n >> m;
	unordered_map<string, pair<int, int>> ma;
	//ma.first ==pattern
	//ma.second.first==pattern_count
	//ma.second.second==0_count
	for (int i = 0; i < n; i++) {
		string str;
		cin >> str;
		ma[str].first++;
		if (ma[str].second == 0) {
			int cnt = 0;
			for (int j = 0; j < str.length(); j++) {
				if (str[j] == '0')
					cnt++;
			}
			ma[str].second = cnt;
		}
	}
	cin >> k;

	for (auto o : ma) {
		int cnt = o.second.second;
		if (cnt <=k && cnt %2 == k%2) {
			answer = max(answer, o.second.first);
			//ma.erase(o.first);
		}
	}
	
	cout << answer;
	return 0;
}