백준 1034 - 램프

문제 설명

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

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 램프의 초기 상태가 주어지면 K번 스위치를 조작하여 모든 램프가 켜진 행의 개수를 최대로 만들어야 한다.

스위치를 한 번 조작하면 해당하는 열의 모든 램프의 상태가 변경된다.

 

해당 문제는 DFS를 사용하면 시간 초과가 발생할 것이다.

즉, K번 스위치를 조작해보는 시뮬레이션은 불가능하다는 뜻이다.

 

그렇다면 직접 불을 조작하지 않으면서 K번 이내에 불이 켜진 행을 최대로 만드는 방법을 찾아내야 한다.

램프의 상태는 2가지 밖에 없다는 것이 가장 큰 힌트이다.

하나의 램프를 2번 조작하면 원래 상태로 돌아간다.

01
10
10

 

램프의 초기 상태가 위와 같다고 하자.

첫 번째 열을 한 번 조작하면 다음과 같다.

11
00
00

여기서 알 수 있는 한 가지는 초기 램프의 상태가 같은 행은 스위치 조작으로 같은 결과를 낸다는 것이다.

따라서 초기 상태가 같은 행은 여러번 계산할 필요가 없다.

 

그리고 행의 모든 램프를 켜기 위해서는 행의 0이 몇 개가 있는지 중요하다.

0이 1개라면 한 번의 조작으로 모든 행을 켤 수 있다.

하지만 이때 K가 2라면 이미 켜져있는 행에 대해 1번 더 조작해야 하므로 해당 행의 램프는 결국 모두 켤 수 없게 된다.

행의 모든 램프를 켠 상태에서 K가 짝수번 남아있다면 특정 열을 껐다 켰다 하여 모든 램프를 켠 상태로 유지할 수 있다.

정리하자면 0의 개수와 K의 홀수인지 아니면 짝수인지가 일치한다면 행의 모든 램프를 켠 상태에서 동일하게 유지할 수 있다는 것이다.

00
11

초기 램프 상태가 위와 같고 K가 999라고 해보자.

K는 홀수이지만 모든 행은 0의 개수가 짝수이다.

따라서 998번 열을 어떻게 조작하든 초기 상태 혹은 초기 상태에서 모든 1과 0이 반전된 결과를 얻을 수 있다.

하지만 남은 1번의 조작으로 하나의 열이 뒤집혀 결국 행의 모든 램프를 켤 수 있는 경우는 없게 된다.

 

이를 식으로 표현한다면 다음과 같다.

// zero = 행의 0의 개수
if (zero <= K && zero % 2 == K % 2)
{
    ans = max(ans, cnt);
}

 

정리하자면 모든 행의 0의 개수를 세고 이를 기록한 뒤 위와 같은 조건으로 개수를 세어보면 정답을 구할 수 있다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N, M, K;
unordered_map<string, pair<int, int>> lamps;

int main()
{
	INPUT_OPTIMIZE;
	
	cin >> N >> M;

	for (int i = 0; i < N; i++)
	{
		string str;
		cin >> str;
		lamps[str].first++;
		
		if (lamps[str].second == 0)
		{
			int cnt = 0;
			for (int j = 0; j < M; j++)
			{
				if (str[j] == '0') cnt++;
			}

			lamps[str].second = cnt;
		}
	}

	cin >> K;

	int ans = 0;
	for (auto& [str, count] : lamps)
	{
		auto& [cnt, zero] = count;
		if (zero <= K && zero % 2 == K % 2)
		{
			ans = max(ans, cnt);
		}
	}

	cout << ans;

	return 0;
}

---