| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 2086 | 611 | 509 | 34.024% |
문제
민이는 각 칸마다 (1*1크기의 정사각형) 램프가 들어있는 직사각형 모양의 탁자를 샀다. 모든 램프는 켜져있거나 꺼져있다. 각 열의 아래에는 스위치가 하나씩 달려있는데, 이 스위치를 누를 때마다 그 열에 있는 램프의 상태가 바뀐다. (켜져있는 램프는 꺼지고, 꺼져있는 램프는 켜진다)
만약 어떤 행에 있는 램프가 모두 켜져있을 때, 그 행이 켜져있다고 말한다. 지민이는 스위치를 K번 누를 것이다. 서로다른 스위치 K개를 누르지 않아도 된다. 지민이는 스위치를 K번 눌러서 켜져있는 행을 최대로 하려고 한다.
지민이의 탁자에 있는 램프의 상태와 K가 주어졌을 때, 스위치를 K번 누른 후에 켜져있는 행의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져있는 상태이다. 마지막 줄에는 K가 주어진다. K는 1,000보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 문제의 정답을 출력한다.
접근
처음 문제를 봤을 때는 어떻게 풀어야 될지 아무런 생각이 나지 않았다.
permutation을 쓰기엔 50은 너무 큰 수이고,
스위치를 키는 갯수를 K 부터 K - 2, ... 1 or 2 개까지 확인이 필요하다.
문제를 다시 한 번 읽어보니 비로소 답이 보였다.
어떤 스위치를 누르더라도 해당 열의 모든 스위치가 반전되는 것이 핵심이었다.
따라서, 스위치를 어떻게 누른다고 해도 값이 서로 다른 행들은 절대로 같아질 수가 없다.
결론적으로, 모든 곳이 같은 값을 가지는 행들의 갯수의 최댓값을 구하면 된다.
하지만 주의할 점이 두 가지 있었다.
첫 번째로, 해당 행의 꺼져 있는 스위치의 갯수가 K개보다 크면 안된다.
두 번째로, K가 짝수면 꺼져 있는 스위치의 갯수가 짝수이고 반대면 홀수여야 된다.
풀이
구현은 크게 어렵지 않았다.
편하게 행들을 비교하기 위해서 string으로 행을 입력받았다.
그리고 오랜만에 쓰는 count 함수를 사용해서 0의 갯수를 세주었다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
int N, M, K, ans = 0;
string arr[50];
bool visited[50];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
MS(visited, false);
CIN2(N, M);
FUP(i, 0, N - 1) CIN(arr[i]);
CIN(K);
FUP(i, 0, N - 1)
{
if (visited[i]) continue;
visited[i] = true;
int cnt = 1;
FUP(j, i + 1, N - 1)
{
if (arr[i] == arr[j])
{
cnt++;
visited[j] = true;
}
}
int off_cnt = count(arr[i].begin(), arr[i].end(), '0');
if (off_cnt <= K && off_cnt % 2 == K % 2) ans = max(ans, cnt);
}
COUT(ans);
return 0;
}