백준 1034번: 램프

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

1034번: 램프

 

 

0. 알고리즘 분류

 브루트포스 알고리즘

 

 

1. 문제

 지민이는 각 칸마다 (1*1크기의 정사각형) 램프가 들어있는 직사각형 모양의 탁자를 샀다. 모든 램프는 켜져있거나 꺼져있다. 각 열의 아래에는 스위치가 하나씩 달려있는데, 이 스위치를 누를 때마다 그 열에 있는 램프의 상태가 바뀐다. (켜져있는 램프는 꺼지고, 꺼져있는 램프는 켜진다) 만약 어떤 행에 있는 램프가 모두 켜져있을 때, 그 행이 켜져있다고 말한다. 지민이는 스위치를 K번 누를 것이다. 서로다른 스위치 K개를 누르지 않아도 된다. 지민이는 스위치를 K번 눌러서 켜져있는 행을 최대로 하려고 한다. 지민이의 탁자에 있는 램프의 상태와 K가 주어졌을 때, 스위치를 K번 누른 후에 켜져있는 행의 최댓값을 구하는 프로그램을 작성하시오.

 

 

2. 풀이

 램프에 대한 입력을 string으로 받아서 정수 배열로 바꿔줬다. 각 행의 0의 개수를 세서, 0의 개수가 k보다 크고 0의 개수가 k랑 같이 짝수이거나 홀수 일때만 이후의 탐색을 돌린다. 0의 개수가 k보다 작거나 0의 개수와 k가 짝수홀수 여부가 다르다면 행을 킬 수 없다.

 

그리고 해당 행과 모양이 같은 행의 개수를 센다. 이를 각 행에 대해 반복해서 켤 수 있는 행의 최댓값을 찾는다.

 

 

3. 코드

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

int table[51][51];
int n, m, k;

int max_func(int x, int y) {
	return (x > y) ? x : y;
}

int main(void) {
	cin >> n >> m;
	
	int i, j, l;
	for (i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		int num = 0;
		for (j = 0; j < m; j++) {
			table[i][j] = temp[j] - ('0' - 0);
			if (table[i][j] == 0)
				num++;
		}
		table[i][m] = num;
	}
	cin >> k;
	
	int ans = 0;
	for (int i = 0; i < n; i++) {
		int max = 1;
		if (table[i][m] > k || table[i][m]%2 != k%2) {
			continue;
		}
		
		for (int j = 0; j < n; j++) {
			if (i != j) {
				for (l = 0; l < m; l++) {
					if (table[i][l] != table[j][l]) {
						break;
					}
				}
				
				if (l >= m)
					max++;
			}
		}
		
		ans = max_func(max, ans);
	}
	
	cout << ans;
	
	return 0;
}