램프

백준 1034

GOLD IV

1. 문제 내용
2. 해결 방안
3. 풀이 코드

---

문제 내용

문제 링크

해결 방안

문제에 따르면 특정 열의 스위치를 누르면 해당 열의 램프의 전원이 반대가 되고, 우리는 K번 스위치를 눌러 켜진 행이 최대가 되는 시점을 찾아야 한다. 켜져있는 행이 있을 때 어느 스위치를 누르던 켜져있던 행이 사라지므로, 켜진 행을 하나 완성했을 때 동시에 켜진 행의 개수가 최대인 시점을 찾아야 한다. 임의의 두 행에 대하여 하나의 행이 켜질 때 다른 행도 켜지려면, 스위치를 누르기 전에 이미 켜져있던 램프의 위치와 개수가 서로 같아야 하므로 두 행은 완전히 동일해야 한다. 결론적으로, 하나의 행에 대해 완전히 동일한 행의 개수가 곧 동시에 켜지는 행이므로, 임의의 행과 동일한 행의 개수가 최대가 되는 시점이 켜질 수 있는 행의 최댓값이다.

때문에, 본 문제는 애드 혹(ad hoc) 문제로 분류되었다.

애드 혹(ad hoc) 문제란?

애드 혹 문제는 그 어원처럼 일반화되지 않은 단순히 현재 문제만을 위한 풀이를 요구한다. 이 문제의 경우에는 브루트포스나 DP처럼 각 경우를 탐색하여 찾는 대신 편법과도 같은 특정 풀이가 존재하기에 애드 혹 문제로 분류된다.

풀이 코드

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    string lamp[50];
    for(int i = 0; i < n; i++)
        cin >> lamp[i];
    
    int k;
    cin >> k;

    int maxCount = 0;
    for(int i = 0; i < n; i++) {
        // 꺼진 램프를 켜기 위해 켜야 하는 스위치 개수
        int switchCount = 0;
        // 자신과 똑같은 행의 개수
        int count = 0;

        for(int j = 0; j < m; j++) {
            if(lamp[i][j] == '0')
                switchCount++;
        }

        // 스위치를 누를 횟수가 켜야 하는 스위치 개수 이상이어야 하며,
        // 해당 행을 켰을 때 남은 눌러야 하는 스위치 개수가 짝수이어야만
        // 해당 행을 켤 수 있다. (짝수 번이면 특정 스위치를 두 번 눌러 횟수만 소진 가능)
        if(switchCount <= k && (k - switchCount) % 2 == 0) {
            // 켜질 수 있는 행과 동일한 행의 개수 확인
            for(int j = 0; j < n; j++) {
                if(lamp[i].compare(lamp[j]) == 0)
                    count++;
            }
        }

        // 최댓값 비교
        if(maxCount < count)
            maxCount = count;
    }

    cout << maxCount << endl;
    return 0;
}

---