[Algorithm] Softeer :: 전광판

https://softeer.ai/practice/6268

Softeer - 현대자동차그룹 SW인재확보플랫폼

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
 
using namespace std;
 
vector<bitset<7>> bits =
{
    bitset<7>("1110111"),
    bitset<7>("0010010"),
    bitset<7>("1011101"),
    bitset<7>("1011011"),
    bitset<7>("0111010"),
    bitset<7>("1101011"),
    bitset<7>("1101111"),
    bitset<7>("1110010"),
    bitset<7>("1111111"),
    bitset<7>("1111011"),
    bitset<7>("0000000")
};
 
int t;
string a, b;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
 
    for (int i = 0; i < t; ++i)
    {
        int answer = 0;
        cin >> a >> b;
 
        string big = a.size() >= b.size() ? a : b;
        string small = a.size() < b.size() ? a : b;
 
        while (!small.empty())
        {
            answer += (bits[small.back() - '0'] ^ bits[big.back() - '0']).count();
 
            big.pop_back();
            small.pop_back();
        }
 
        while (!big.empty())
        {
            answer += (bits[big.back() - '0'] ^ bits[10]).count();
            big.pop_back();
        }
 
        cout << answer << endl;
    }
}
   
 
 
 

 

현대 오토에버 코딩테스트 때문에 소프티어사이트에서 문제 좀 풀다가 안풀어본 유형이라 작성해본다.

아마 비슷한 문제가 백준에도 분명 있을거라 생각된다.

 

전광판의 각 전구를 몇개를 껐다켰다해야하는지 구해야하는 문제인데, 각 숫자마다의 전구상태를 이진수형태, 즉 bit로 표현해서 미리 룩업테이블로 작성해놓으면 편하게 풀 수 있다.

아예 다 꺼야하는 경우도 있으니 해당경우도 추가해줘야한다.

그리고 3에서 1로 갈때의 전구조작횟수나, 1에서 3으로 갈때의 전구조작횟수는 같다.

 

그래서 저렇게 룩업테이블로 먼저 각 숫자의비트를 구해놓은 후, 자리수가 더 작은 숫자를 기준으로 1의자리수부터 xor연산을 통해 전구조작횟수를 구한다. xor는 서로 다를때 1이되기 때문에 전구조작이라는 행위랑 매핑된다.

이 1의 개수가 곧 전구조작횟수가 되기 때문에 answer에 누적시켜준다.

 

이후 자리수가 더 큰 숫자의 문자열에 남아있는 숫자개수만큼, 해당숫자들을 다 꺼버리는 전구조작횟수를 누적시켜주면 된다.