[알고리즘 문제] 백준1034 - 램프

www.acmicpc.net/problem/1034

1034번: 램프

처음에 재귀로 풀었다가 시간초과가 나왔습니다. 재귀를 이용해서 몇가지 방법으로 풀어봤는데 계속 시간초과가 나와서 다른 사람의 풀이를 참고하였습니다.

 

문제에서 구하는 값은 모든 열이 켜져있는 행의 최대개수를 구하는 문제입니다. 여기서 중요한 것은 모든 열이 켜져있어야 합니다. 대신에 키고/끄고할 수 있는 기준은 "열"입니다.  여기서 생각해볼 수 있는 점은 1행의 전구패턴과 2행의 전구패턴이 같다면 1행의 전구가 모두 켜질 때 2행도 모두 켜지겠죠. 여기서 2개의 조건이 추가됩니다.

 

1. n행의 꺼진 전구의 개수는 k보다 작거나 같아야 한다

2. n행의 꺼진 전구의 개수와 k가 모두 짝수/홀수 여야합니다.

 

1번의 조건은 당연한 얘기입니다. 전구가 모두 "켜진"행이여야 하는데 꺼진 전구의 개수보다 스위치가 더 많으면 안되겠죠.

2번 조건은 조금 생각해 봐야하는데, 예를 들어 꺼진 전구를 홀수번 반복하면 켜지고, 짝수번 반복하면 꺼집니다. 이는 켜진 전구도 마찬가지고 결국 홀수번 스위치를 누르면 반대가 되고 짝수번 스위치를 누르면 같은 상태가 됩니다. 때문에 k와 행에서 꺼진 전구의 개수가 같아야(같은 홀수/짝수)합니다.

 

위의 1,2조건이 만족되었다면 n번째 행을 기준으로 다른 행을 검색하면 됩니다.

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int height, width;
    int ans = -1;
    string arr[50];

    cin >> height >> width;

    for (int y = 0; y < height; y++)
    {
        cin >> arr[y];
    }

    int k;
    cin >> k;

    for (int i = 0; i < height; i++)
    {
        int zeroCount = 0;
        for (int h = 0; h < width; h++)
        {
            if (arr[i][h] == '0')
            {
                zeroCount++;
            }
        }
        int sum = 0;
        if (zeroCount <= k && zeroCount % 2 == k % 2)
        {
            for (int y = 0; y < height; y++)
            {
                if (arr[i] == arr[y])
                {
                    sum++;
                }
            }
        }
        ans = max(sum, ans);
    }
    cout << ans;
    return 0;
}