BOJ 1034 램프

김재섭·2021년 4월 17일

BOJ 1034 BOJ 램프 백준 1034 백준 램프

백준

목록 보기

6/10

문제

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

아이디어

첫번째 아이디어

단순히 bool array로 램프를 구성해서 BFS로 모든 경우의 수를 뽑아낸다.

시간초과, columnFlip의 시간을 줄이면 되지 않을까 ?

두번째 아이디어

columnFlip의 시간을 줄이기 위해 비트마스킹을 사용해보자!
최대 크기가 50 * 50이므로 long long 배열을 만들어서 비트마스킹
Flip을 not 연산자(~)으로 구현했다.
열에 not 연산자를 사용하기 위해 행과 열을 반대로 입력 받았다.

시간초과, 아예 다른 방법이 필요하다

세번째 아이디어

먼저 푼 친구에게 물어봐서 힌트를 얻음
비트들이 있을 때 문자열 자체를 비교해서 같은 자리의 0의 개수를 카운트했다고 한다.
아차 싶었다, 머리 속에 그려보니 다음과 같은 단계를 도출할 수 있었다.

꼭 서로 다른 열을 Flip시키는 것이 아니므로 K를 2씩 감소시키면서 K의 개수와 해당 행의 0의 개수가 같은지 비교한다.
0의 개수가 같은 문자열을 전부 다른 리스트에 추가한다.
리스트에서 같은 문자열이 몇 개인지 최대 개수를 뽑아낸다.

코드

첫번째 코드

#include <stdio.h>
#include <vector>

using namespace std;

vector<vector<bool>> V;
vector<vector<bool>> check;
int N, M, K;
int ANS;
int input;

void columnFlip(vector<vector<bool>> &V, int idx) {
    for (int i = 0; i < N; i++) {
        V[i][idx] = !V[i][idx];
    }
}

void findAnswer(vector<vector<bool>> V, vector<vector<bool>> check, int depth) {
    if (depth == K) {
        int countVal = 0;

        for (int i = 0; i < N; i++) {
            bool rightON = true;

            for (int j = 0; j < M; j++) {
                if (V[i][j] == 0) {
                    rightON = false;
                    break;
                }
            }
            if (rightON)
                countVal++;
        }

        if (countVal > ANS)
            ANS = countVal;

        return ;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (check[i][j] == 0) {
                columnFlip(V, i);
                check[i][j] = 1;

                findAnswer(V, check, depth+1);

                columnFlip(V, i);
                check[i][j] = 0;
            }
        }
    }
}

int main(void)
{
    freopen("input_1.txt", "r", stdin);
    scanf("%d %d", &N, &M);

    V.resize(N);
    check.resize(N);

    for (int i = 0; i < N; i++) {
        V[i].resize(M);
        check[i].resize(M);
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%1d", &input);

            if (input == 0)
                V[i][j] = 0;
            else
                V[i][j] = 1;
        }
    }

    scanf("%d", &K);

    findAnswer(V, check, 0);

    printf("%d\n", ANS);

    return 0;
}

두번째 코드

#include <iostream>
#include <string>

using namespace std;

string input;
int N, M, K;
long long bits[50];
int ANS;

void BFS(bool check[50][50], int depth) {
    if (depth == K) {
        int countVal = 0;

        for (int i = 0; i < N; i++) {
            bool rightON = true;

            for (int j = 0; j < M; j++) { // 같은 행의 비트가 전부 1인지 비교
                if (!(bits[j] & (1 << i))) {
                    rightON = false;
                    break;
                }
            }

            if (rightON) // 전부 켜져 있다면 count
                countVal++;
        }

        if (countVal > ANS)
            ANS = countVal;

        return;
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (check[i][j] == 0) {
                bits[i] = ~bits[i]; // 해당 열 bit flip
                check[i][j] = 1;

                BFS(check, depth+1);

                bits[i] = ~bits[i];
                check[i][j] = 0;
            }
        }
    }
}

int main(void)
{
    bool check[50][50] = {{0,},};

    freopen("input_1.txt", "r", stdin);

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        cin >> input;

        for (int j = 0; j < M; j++) {
            if (input[j] == '1')
                bits[j] |= (1 << i);
        }
    }

    cin >> K;
    BFS(check, 0);

    cout << ANS << endl;

    return 0;
}

세번째 코드

N, M = map(int, input().split())
bits = []
ANS = 0 
string = ''

for i in range(N):
    string = input()

    bits.append(string)

K = int(input())

for i in range(K, -1, -2):
    lst = []
    for j in range(N):
        if i == bits[j].count('0'):
            lst.append(bits[j])

    if len(lst) != 0:
        ANS = max(ANS, max([lst.count(s) for s in lst]))

print(ANS)