[백준] 1034번_램프 C++

02 Apr 2023 in Study on Coding Test

완전탐색을 활용하는 문제

정답제출코드

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

int N, M, K;
int ans = 0;
vector<string> Switch;
map<string, int> SamePattern;

int m_max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
    {
        string s;
        cin >> s;

        Switch.push_back(s);
    }

    cin >> K;

    for (int i = 0; i < N; ++i)
    {
        int counter = 0;
        for (int j = 0; j < M; ++j)
        {
            if (Switch[i][j] == '0')
                counter++;
        }

        if (counter > K || (K % 2 != counter % 2))
            continue;

        auto iter = SamePattern.find(Switch[i]);
        if (iter == SamePattern.end())
            SamePattern.insert({Switch[i], 1});
        else
            iter->second++;
    }

    for (auto i : SamePattern)
        ans = m_max(ans, i.second);

    cout << ans;

    return 0;
}

참고링크를 참고해서 풀었다.

핵심 쟁점은 K값과 행에서 켜야하는 스위치의 수의 홀짝 여부가 같은가를 따져야 하고,

서로 같은 패턴으로 켜져거나 꺼져있는 상태인 행의 개수가 몇 개인지를 따져야 하는 것이었다.

서로 같은 패턴으로 되어있는 상태인 행은 map을 이용해서 구현하였다.

오답제출코드(시간초과)

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int N, M, K;
int ans = 0;
vector<string> Switch;

void backtrack(int depth);
void CmpAns();

int main()
{
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
    {
        string s;
        cin >> s;

        Switch.push_back(s);
    }

    cin >> K;

    backtrack(0);

    cout << ans;

    return 0;
}

void backtrack(int depth)
{
    if (depth == K)
    {
        CmpAns();
        return;
    }
        
    
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (Switch[i][j] == '0')
            {
                Switch[i][j] = '1';
                backtrack(depth+1);
                Switch[i][j] = '0';
            }
            else if (Switch[i][j] == '1')
            {
                Switch[i][j] = '0';
                backtrack(depth+1);
                Switch[i][j] = '1';
            }
        }
    }
}

void CmpAns()
{
    int row = 0;
    for (int i = 0; i < N; ++i)
    {
        bool flag = true;
        for (int j = 0; j < M; ++j)
        {
            if (Switch[i][j] == '0')
            {
                flag = false;
                break;
            }
        }
        if (flag)
            row++;
    }

    if (row > ans)
        ans = row;
    return;
}

제일 먼저 떠올렸던 방법은 백트래킹이었다.

그런데 문제는 이거를 백트래킹으로 풀면은 당연히 시간초과가 날 수 밖에 없다는 생각이 들었지만

일단은 시뮬레이션을 해보았다.

그리고 역시나.. 999번을 누르게 된다면 작동시간이 10초가 넘게 걸린다.

여기서 분명 수학적인 규칙이 있을 것이라 생각하였다.