[1034] 램프

문제 링크 : https://www.acmicpc.net/problem/1034

1034 - 램프

본문

지민이는 각 칸마다 ($1 \times 1$크기의 정사각형) 램프가 들어있는 직사각형 모양의 탁자를 샀다. 모든 램프는 켜져있거나 꺼져있다. 각 열의 아래에는 스위치가 하나씩 달려있는데, 이 스위치를 누를 때마다 그 열에 있는 램프의 상태가 바뀐다. 켜져있는 램프는 꺼지고, 꺼져있는 램프는 켜진다)

만약 어떤 행에 있는 램프가 모두 켜져있을 때, 그 행이 켜져있다고 말한다. 지민이는 스위치를 $K$번 누를 것이다. 서로다른 스위치 $K$개를 누르지 않아도 된다. 지민이는 스위치를 $K$번 눌러서 켜져있는 행을 최대로 하려고 한다.

지민이의 탁자에 있는 램프의 상태와 $K$가 주어졌을 때, 스위치를 $K$번 누른 후에 켜져있는 행의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 $N$과 $M$이 주어진다. $N$은 행의 개수이고, $M$은 열의 개수이다. $N$과 $M$은 $50$보다 작거나 같은 자연수이다. 둘째 줄부터 $N$개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져있는 상태이다. 마지막 줄에는 $K$가 주어진다. $K$는 $1\,000$보다 작거나 같은 자연수 또는 $0$이다.

출력

첫째 줄에 문제의 정답을 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

---

풀이

다시 풀어보는데도 못 푼 문제다. 예나 지금이나 아이디어를 생각하는게 나로서는 불가능했다. 사실 풀면서 이게 이 난이도의 문제가 맞는지도 계속해서 의심했던 문제다.

내가 못풀었던 이유는, 가장 중요한 특징을 깨닫지 못했기 때문이다. 그것은 “서로 다른 형태의 행을 모두 켜는 방법이 존재하지 않는다“는 것. 스위치가 모든 열에 대하여 램프를 끄고 켜기 때문에, 서로 다른 형태의 행에 대해서는 하나가 켜지면 다른 하나가 꺼지는 상황이 필연적으로 연출된다는 점이었다. 이것을 찾아낸 다음에야 이 문제의 난이도가 이해가 가는 수준.

그래서, 스위치를 어떤 것을 끄고 켤 것인지를 확인하는 것이 아니라, 특정 행에 대하여 램프를 다 켤 수 있는지 확인하고, 같은 형태의 행이 있는지 검사하는 과정만 만들어내면 풀어낼 수 있는 문제였다. 스위치는 아무거나 껐다 켰다 할 수 있으므로, 램프를 다 켤수 있는 조건은 “꺼져있는 램프의 수가 스위치를 누를 수 있는 횟수보다 적거나 같고, 그 차이가 2의 베수“이다. 차이가 2의 배수여야 껐다 켰다 할 수 있기 때문.

행의 구성이 같은지 확인하는 방법은 문자열 비교 방법을 사용하면 된다. 헤더의 `strcmp`를 사용해도 된다. 같은 행의 개수만 세고, 그 행을 켤 수 있는 조건이 부합한다면 최종 개수에 업데이트해주면 된다.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2023 / 4 / 17

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_IDX 50
char grid[MAX_IDX][MAX_IDX + 1];
int n, m, k;

const char ON = '1';
const char OFF = '0';

bool string_compare(int a, int b) {
    for (int i = 0; i < m; ++i) {
        if (grid[a][i] != grid[b][i]) {
            return false;
        }
    }
    return true;
}

#define max(a, b) (((a) > (b)) ? (a) : (b))
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i) {
        scanf("%s", grid[i]);
    }
    scanf("%d", &k);

    int result = 0;
    for (int i = 0; i < n; ++i) {
        int offCount = 0;
        for (int j = 0; j < m; ++j) {
            offCount += (grid[i][j] == OFF);
        }

        if (offCount <= k && offCount % 2 == k % 2) {
            int sameCount = 1;
            for (int j = 0; j < i; ++j) {
                sameCount += (string_compare(i, j));
            }
            result = max(result, sameCount);
        }
    }

    printf("%d", result);
    return 0;
}