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

문제 링크

1034번: 램프

문제 요약

탁자의 각 칸에 램프가 놓여 있다. 빈 칸은 존재하지 않고 램프는 켜져있거나 꺼져있다. 특정 열의 버튼을 누르면 해당 열의 모든 램프의 상태가 반전이 된다. 이때, 버튼을 K번 눌러서 모든 램프가 켜져 있는 행의 수의 최댓값을 구해야 한다.

접근 방법

먼저 모든 행을 문자열로 받아서 저장을 해줍니다. 그리고 반복문을 돌면서 행에서 켜야하는 램프의 수를 세줍니다. 만약 켜야하는 램프의 수가 K보다 크면 이후의 절차를 건너뜁니다. 또 K와 홀수, 짝수 여부가 다른 경우에도 건너뜁니다. 예를 들어, 켜야하는 램프의 수가 5개로 홀수이고, K가 6으로 짝수이면 해당 행은 건너 뛰어주면 됩니다.

켜야하는 램프의 수가 K보다 크다면 그 행은 어떻게 하더라도 모두 켜질 수가 없습니다. 램프의 수가 홀수이고 K가 짝수이거나, 램프의 수가 짝수이고 K가 홀수인 경우에도 불가능하다는 것을 생각해 볼 수 있습니다.

이제 std::map에 저장을 해주면 되는데 key는 문자열, value는 같은 패턴의 문자열의 수로 해줍니다. 마지막으로 맵 내의 value의 최댓값을 찾아 출력해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n, m, k;
	cin >> n >> m;

	vector<string> v;
	map<string, int> table;

	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		v.push_back(str);
	}

	cin >> k;
	for (auto& i : v)
	{
		int zero = 0;
		for (auto& j : i)
			if (j == '0')
				zero++;

		if (zero > k || (zero % 2 != k % 2))
			continue;

		if (table.find(i) == table.end())
			table.insert({ i, 1 });
		else
			table[i]++;
	}

	int ans = 0;
	for (auto& j : table)
		ans = max(ans, j.second);
	cout << ans;
	return 0;
}