1034 램프(C++)
문제를 도전하다 모르겠으면 알고리즘 분류, 풀이, 코드 순서로 보는데
코드까지 봐도 이해가 안됬던 문제
고양이 좀 놀아주고 다시 보니 풀이 자체는 쉽지만
아이디어를 떠올리는것이 어려운 문제였다
1. 문제
간단 설명
N, M 사이즈의 탁자에
각 칸별로 램프가 주어진다
한 열에 스위치를 누르면 해당 열의 램프는 꺼진것은 켜지고, 켜진것은 꺼진다
한 행에 램프가 모두 켜져있을 때, 그 행이 켜져있다고 말한다
스위치를 K개 눌렀을 때, 켜져 있는 행의 최대값을 구하는 문제
2. 문제 분석
주의점
- bruteforce로 직접 계산하면 2^50 이 걸려 시간초과가 발생한다
알고리즘
1.어떤 행 i, j 가 K번 스위치를 눌렀을 때, 두 행 모두 켜져있는 상태가 되기 위해서는 두 행의 초기상태가 같은 경우에만 가능하다.
ex) 위와 같은 다섯가지 행 011, 101, 011, 100, 011 이 있을 때
1번 열을 활성화 하면 다음과 같이 111, 001, 111, 000, 111 로 바뀐다
011과 101만 봤을때, 두 행을 어떻게 조작하더라도 두 행이 모두 활성화 시키는 것은 불가능하다
2.i 행의 0의 개수가 K보다 많다면, 그 행은 활성화 시키는게 불가능하다
즉, 100처럼 두개를 켜야하는데, K가 1이라 하나밖에 킬 수 없다면, 활성화 시키는것이 불가능 하다는 뜻
3.0의 개수가 K보다 작으면 0의 개수가 짝수인지 홀수인지 체크한다
0의 개수가 짝수인데, K가 홀수라면 행을 활성화 하는게 불가능하다
ex) i번째 행이 100인데, K=3이라면, 어떤 방식으로도 행을 활성화 시키는것이 불가능하다
마찬가지로 0의 개수가 홀수인데, K가 짝수라면, 행을 활성화 하는게 불가능하다
ex) i번째 행이 101 인데, K=2라면, 행을 활성화 시키는게 불가능함
1번, 2번, 3번을 이용하여 정리하면
1
2
3
4
5
6
1. 1번 행 부터, N번행 까지 다음을 확인한다
2. 각 행에 0이 몇개 있는지 체크한다
3. 만약 0의 개수가 K보다 많다면 불가능하므로 다음행으로 넘어감
4. 현재 행의 불을 킬 수 있는지 확인해본다
5. 현재 행과 같은 구성의 행이 몇개 있는지 체크한다
6. 2~5번 과정을 반복하여 최대로 구할 수 있는 행의 개수를 구하여 출력한다
필요변수
int N, M, K정답의 개수를 저장할
int ans램프의 상태를 저장할
lamp배열. 여기선 문자열을 사용했다
3. 소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int N, M, K, ans;
string lamp[50];
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++)
cin >> lamp[i];
cin >> K;
for (int i = 0; i < N; i++) {
auto s = lamp[i];
int cnt = 0;
for (int j = 0; j < M; j++) {
if (s[j] == '0') cnt++;
}
if (cnt > K || cnt % 2 != K % 2) continue;
int sameCnt = 0;
for (int j = 0; j < N; j++)
if (s == lamp[j]) sameCnt++;
ans = max(ans, sameCnt);
}
printf("%d", ans);
return 0;
}
참고 : https://kosaf04pyh.tistory.com/304, https://leesh111112.tistory.com/369