[ 백준 1034 ] 램프 (C++) - 패턴

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 처음에는 50X50의 문제여서 완전탐색으로 풀 수 있는 문제라 생각했는데, 1000번의 열의 스위치를 킬 수 있다는 선택지 때문에, 2^50의 가짓수라 모든 경우를 찾아볼 수 없는 문제였다.
2. 문제의 조건을 보았을 때, K번을 반드시 눌러야 하므로 예제에서 열이 1개일 때, 짝수번이면 변화가 없는 것을 알 수 있다. 이 점에 유의해야 한다.
3. 모든 경우를 찾을 수 없다면, 경우를 줄여야 하는데, 이때, 패턴을 찾는 것이 그 방법이다. 예를 들어서 100 100 101 110 이런 식이라고 하자. 100과 101, 110은 같은 열의 솟자가 바뀌기 때문에 최종적으로 모두 1인경우가 나올 수가 없다. 따라서 100 패턴은 2개, 101 패턴은 1개, 110 패턴도 1개 이렇게 분리해야 한다.
4. 3번에서의 패턴을 내가 2번 누를 수 있다고 가정하자. 그러면 111 111 110 101 이렇게 되어 정답은 2가 될 것이다. 하지만, 3번이라면? 100을 111로 만들 수 없다. 이는 (K-0의 개수)%2==0 이 성립해야 패턴을 모두 램프가 켜진 것으로 만들 수 있다는 것을 의미한다.
5. 마지막으로 1000000000000이라는 패턴만 주어진다고 할 때, K가 0의 개수보다 작다면 해당 패턴을 모두 1로 채울 수 없을 것이다.
6. 3번 과정에서 패턴의 개수를 구한 다음에, 4,5번의 예외처리를 하면 램프가 모두 켜져 있는 행의 최댓값을 구할 수 있다.

---

⭐️ 정답 코드 및 주석

#include <iostream>
#include <map>

using namespace std;

int N, M, K;
int answer = 0;

map<string, pair<int, int>> lampsPattern;  // {pattern, {0의 갯수, 패턴의 갯수}}

void input() {
    cin >> N >> M;
    string pattern;
    for (int x = 0; x < N; x++) { // 패턴을 받아와 이미 있는 패턴이면 패턴의 갯수를 늘려주고, 아니면 새로운 패턴 map에 넣어준다.
        cin >> pattern; 
        if (lampsPattern.find(pattern) != lampsPattern.end()) {
            lampsPattern[pattern].second++;
        } else {
            int zeroCount = 0;
            for (int i = 0; i < pattern.size(); i++) {
                if (pattern[i] == '0') zeroCount++;
            }
            lampsPattern.insert({pattern, {zeroCount, 1}});
        }
    }
    cin >> K;
}

void sol() {
    for (auto pattern : lampsPattern) {
        string str = pattern.first;
        int zeroCount = pattern.second.first;
        int patternCount = pattern.second.second;

        cout << str << " " << zeroCount << ", " << patternCount << endl;

        if (patternCount <= answer || zeroCount > K) continue;
        if ((zeroCount - K) % 2 != 0) continue;

        answer = patternCount;
    }

    cout << answer;
}

int main() {
    input();
    sol();
    return 0;
}

---

🤔 문제 후기

처음에는 K값도 50 이하인 줄 알고, 브루트포스로 풀 수 있겠다 생각하여 패턴이 바뀌면 해당 열의 스위치의 ON/OFF 여부에 따라 판별하려고 했다. 그래서 시간 초과가 나왔고, 문제를 다시 보니 K가 최대 1000 임을 알았다. 처음에는 문제를 풀 아이디어를 생각하지 못했는데, 예제를 보고 패턴을 찾을 수 있다고 생각하였는데, 사실 예제 5번이 없었다면 푸는 방법을 생각하기 어려웠을 것 같은 문제였다.

(물론 내가 부트캠프를 마치고 너무 오랜만에 알고리즘 문제를 푼 영향도 있을 것 같다.)