[백준/C++] 램프

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 특정 열의 램프들을 반전 시키는 방법을 K번 실시했을 때, 모든 행의 램프가 켜진 경우가 가장 많은 수를 구해야 한다.

 

이 문제에서는 램프가 가장 많이 켜진 경우를 찾기 위해 모든 경우를 탐색해봐야 하는데 이때, 모든 경우를 찾기 위한 기준을 잘 정해야 한다.

 

특정 열의 램프들을 끄거나 키는 것을 기준으로 잡게 되면 2^n의 시간복잡도가 나타나고 중복이 발생하게 된다.

 

잘 생각해보면 반대로 특정 행의 램프들을 전부 키도록 한 다음 그때, 몇 행의 램프가 켜져있는지 비교하는 방법으로 쉽게 문제를 풀 수 있다.

(왜냐하면 같은 열에 있는 램프들은 전부 불이 반전되는 것에 연결되어 있다. 그렇기 때문에 한 행의 램프가 전부 켜지는 경우에 다른 행의 램프도 켜지거나 꺼지는 게 정해지기 때문이다.)

 

그러므로 우리가 찾는 가장 많은 행의 램프가 켜져있는 경우를 구하려면, 특정 행의 램프를 전부 킬 수 있는지 확인하고 전부 켜진다면, 총 몇개의 행의 램프가 켜져있는지 비교해 가장 큰 값을 return하면 된다.

 

+ 특정 행의 램프가 켜질 수 있는지가 기준이 되는 이유는 가장 많은 행의 램프가 켜지는 경우는 결국 어떤 행 i의 램프가 전부 켜지는 경우라고 볼 수 있다. 그러므로 i행의 램프가 켜진 경우들만 비교하면 가장 많이 램프가 켜져있는 경우를 구할 수 있다.

 

 

​

[아이디어 정리]

1. 특정 행의 램프들이 켜지거나 꺼지는 게 정해지면, 자동으로 다른 행의 램프가 켜지거나 꺼지는 경우도 정해진다.
2. 이를 이용해 1~N행의 램프를 전부 킬 수 있는지 확인하고, i번째 행의 램프를 킬 수 있다면 그 때 몇 개의 행에 램프가 켜져있는지 비교한다.
3.  최종적으로 가장 많은 행의 수를 출력한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
using namespace std;


int calc(vector<vector<bool>>& tLamp)  // 몇개가 켜져있는지
{
	int answer = 0;

	for (int i = 0; i < tLamp.size(); i++) 
	{
		answer += 1;
		for (int j = 0; j < tLamp[i].size(); j++) 
		{
			if (!tLamp[i][j]) {
				answer -= 1;
				break;
			}
		}
	}
	return answer;
}


int calc2(vector<vector<bool>> tLamp, int N, int k) 
{ // N번째 행을 무조건 켜지도록 한다.
	for (int i = 0; i < tLamp[N].size(); i++)
	{
		if (!tLamp[N][i]) {
			if (k>0)
			{
				for (int j = 0; j < tLamp.size(); j++) 
				{
					tLamp[j][i] = !tLamp[j][i];
				}
				k--;
			}
			else
			{
				return 0;
			}
		}
	}
	if (k%2==0){
		return calc(tLamp);
	}
	else {
		return 0;
	}
}


int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, M;
	cin >> N >> M;
	vector<vector<bool>> lamp(N, vector<bool>(M, false));
	string str;
	for (int i = 0; i < N; i++) 
	{
		cin >> str;
		for (int j = 0; j < M; j++) 
		{
			if (str[j] == '1') {
				lamp[i][j] = true;
			}
		}
	}
	int k;
	cin >> k;
	int maxAns = 0;
	for (int i = 0; i < N; i++) 
	{
		maxAns = max(maxAns, calc2(lamp, i, k));
	}
	cout << maxAns;

	return 0;
}

 

---

처음에 고민을 하다가 한 행의 상태가 결정되면 다른 행의 상태도 전부 결정된다는 것을 빠르게 눈치 챌 수 있었다.

덕분에 쉽게 풀 수 있는 문제였다.

 

1034번: 램프