[알고리즘] 램프

구현 방식

• 애드혹은 해당 문제를 풀기위한 정형적인 알고리즘을 적용하지 않고 해결할 수 있는 문제의 유형으로
• 보통 그리디, 구현, 수학 유형의 문제로 출제된다.
• 해당 문제는 동일한 행 구조를 띈 것끼리 묶은 다음에 0의 개수(꺼져있는)를 세준다. 0 의개수가 K개인 것중 가장 여러번 나오는 행의 개수를 세준다.
• 다만, 동일 스위치를 눌러서 K번을 맞춰줄 수 있으므로 K개 뿐만아니라 K-2 , K-4 , …, 0 개인 경우까지 생각해야한다.

코드

• 최종 코드는 아래와 같다.

#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;

void solution(int N, int M, int K, unordered_map<string,pair<int,int>>& freqRow);

int main() {
    int N, M, K;
    unordered_map<string, pair<int,int>> freqRow;
    cin >> N >> M;

    string r;
    for(int i = 0; i < N; i++)
    {
        cin >> r;
        if(freqRow.find(r) == freqRow.end())
            freqRow[r] = {count(r.begin(), r.end(), '0'), 1};
        else
            freqRow[r].second++;
    }

    cin >> K;

    solution(N,M,K,freqRow);

    return 0;
}

// 0의 개수가 k개 , k-2개,..., 0개 인 것 중에 빈도수가 가장 높은 것 탐색

void solution(int N, int M, int K, unordered_map<string,pair<int,int>>& freqRow)
{
    int result = 0;
    for(int k = K; 0 <= k; k-= 2)
    {
        for(auto& row : freqRow)
        {
            if(row.second.first == k)
                result = max(row.second.second, result);
        }
    }

    cout << result;
}