글 읽기 - 램프 문제 어디가 틀렸는지 못찾겠습니다

jaykay 7년 전 0

생각해볼 수 있는 예제는 다 넣어봤는데 어느 부분이 틀렸는지 못찾겠네요.

도움 주시면 감사하겠습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>

#include <string>
using namespace std;

const int MAX_NM = 50;

int n, m, k;

int howManyLampsAreTurnedOn(const bool lamps[MAX_NM][MAX_NM])
{
	int count = 0;
	for (int i = 0; i < n; i++)
	{
		bool isAnswer = true;
		for (int j = 0; j < m; j++)
		{
			if (lamps[i][j] == false)
			{
				isAnswer = false;
				break;
			}
		}
		if (isAnswer)
			count++;
	}
	return count;
}
void turnLamps(bool lamps[MAX_NM][MAX_NM], int row)
{
	for (int i = 0; i < n; i++)
		lamps[i][row] = !lamps[i][row];
}

int greedy(const bool lamps[MAX_NM][MAX_NM], int c)
{
	int ret = 0;
	for (int64_t i = 0; i < (1 << m); i++)
	{
		int bitCount = 0;
		for (int j = 0; j < m; j++)
		{
			if ((i >> j) & 1)
				bitCount++;
		}
		if (bitCount > c)
			continue;
		if (bitCount != c && bitCount % 2 != c % 2)
			continue;

		bool tmpLamps[MAX_NM][MAX_NM];
		memset(tmpLamps, 0, sizeof(tmpLamps));
		for (int c = 0; c < n; c++)
		{
			for (int r = 0; r < m; r++)
				tmpLamps[c][r] = lamps[c][r];
		}

		for (int j = 0; j < m; j++)
		{
			if ((i >> j) & 1)
				turnLamps(tmpLamps, j);
		}
		ret = max(ret, howManyLampsAreTurnedOn(tmpLamps));
	}
	return ret;
}

int main()
{
	bool lamps[MAX_NM][MAX_NM];
	memset(lamps, 0, sizeof(lamps));
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		string str;
		cin >> str;
		for (int j = 0; j < m; j++)
		{
			if (str[j] == '1')
				lamps[i][j] = true;
		}
	}
	cin >> k;
	cout << greedy(lamps, k) << endl;
	return 0;
}

zlzmsrhak 7년 전 0

1. 42번재 줄에서 1<<i가 1ll << i로 바뀌어야 합니다.

(컴파일을 해 보지는 않았지만 Warning에 관련 내용이 출력 될 것 같은데, Warning을 확인하는 것도 좋은 디버깅 습관입니다.)

2. 시간복잡도가 O(2^M * NM)이기 때문에, 고친 후에도 시간초과가 발생합니다.

더 좋은 알고리즘으로 문제를 해결해야 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

램프 문제 어디가 틀렸는지 못찾겠습니다

jaykay 7년 전 0

zlzmsrhak 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말