[백준, C++] 22251 - 빌런 호석

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

22251번: 빌런 호석

 

문제 분석

진짜 너무너무 너무너무 귀찮은 문제이다. 특별한 알고리즘을 필요로 하지는 않는다. 그래서 문제 분석 칸이 짧다. 그냥 구현이고, 브루트포스이다. 코드를 작성하는 내내 귀찮아서 죽을 뻔 했다(이런 말을 해도 되나 ?).

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, k, p, x;
bool isOn[10][7];
vector<int> changables[10];
vector<int> xVec;
vector<int> iVec;
int result;

void getInput();
void solve();
void printResult();

void initIsOn();
void xToVec();
void iToVec(int);
int getDiff();

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    getInput();
    solve();
    printResult();

    return 0;
}

void getInput() {
    cin >> n >> k >> p >> x;
}

void initIsOn() {
    isOn[0][0] = true;
    isOn[2][0] = true;
    isOn[3][0] = true;
    isOn[5][0] = true;
    isOn[6][0] = true;
    isOn[7][0] = true;
    isOn[8][0] = true;
    isOn[9][0] = true;
    
    isOn[0][1] = true;
    isOn[1][1] = true;
    isOn[2][1] = true;
    isOn[3][1] = true;
    isOn[4][1] = true;
    isOn[7][1] = true;
    isOn[8][1] = true;
    isOn[9][1] = true;

    isOn[0][2] = true;
    isOn[1][2] = true;
    isOn[3][2] = true;
    isOn[4][2] = true;
    isOn[5][2] = true;
    isOn[6][2] = true;
    isOn[7][2] = true;
    isOn[8][2] = true;
    isOn[9][2] = true;

    isOn[0][3] = true;
    isOn[2][3] = true;
    isOn[3][3] = true;
    isOn[5][3] = true;
    isOn[6][3] = true;
    isOn[8][3] = true;
    isOn[9][3] = true;

    isOn[0][4] = true;
    isOn[2][4] = true;
    isOn[6][4] = true;
    isOn[8][4] = true;
    
    isOn[0][5] = true;
    isOn[4][5] = true;
    isOn[5][5] = true;
    isOn[6][5] = true;
    isOn[8][5] = true;
    isOn[9][5] = true;

    isOn[2][6] = true;
    isOn[3][6] = true;
    isOn[4][6] = true;
    isOn[5][6] = true;
    isOn[6][6] = true;
    isOn[8][6] = true;
    isOn[9][6] = true;
}

void xToVec() {
    int copiedX = x;
    for (int i = 0; i < k; i++) {
        xVec.push_back(copiedX % 10);
        copiedX /= 10;
    }
    reverse(xVec.begin(), xVec.end());
}

void iToVec(int num) {
    iVec.clear();
    for (int i = 0; i < k; i++) {
        iVec.push_back(num % 10);
        num /= 10;
    }
    reverse(iVec.begin(), iVec.end());
}

int getDiff(int num1, int num2) {
    int diff = 0;
    for (int i = 0; i < 7; i++) {
        if (isOn[num1][i] != isOn[num2][i]) {
            diff++;
        }
    }

    return diff;
}

void solve() {
    initIsOn();
    xToVec();

    for (int i = 1; i <= n; i++) {
        if (i == x) {
            continue;
        }

        iToVec(i);
        int diff = 0;
        for (int j = 0; j < xVec.size(); j++) {
            diff += getDiff(xVec[j], iVec[j]);
        }

        if (diff <= p) {
            result++;
        }
    }
}

void printResult() {
    cout << result << "\n";
}

 

코드 설명

isOn 배열은 각 숫자가 디스플레이에 표시될 때, 표시등에 불이 들어왔으면 true이고 아니면 false로 표현하기 위해 존재한다. xVec은 입력으로 주어진 x를 [0, 0, 1, 2, 3] 과 같이 하나하나 분리하기 위해 두었고, iVec은 뒤에 반복문에서 1부터 n까지 모든 층에 대해 x를 i로 바꿀 수 있는지 체크하는데, 그 때 i를 xVec처럼 사용하기 위해 두었다.

 

initIsOn()을 작성할 때 좀 현타가 왔는데, isOn[i][j]에서 i는 숫자이고, j는 표시등이다. isOn[i][j] == true라는 것은, i를 표시할 때 j번 표시등에 불이 들어온다는 것을 의미한다.

 

getDiff()는 num1과 num2를 파라미터로 받아서, num1을 num2로 변환하기 위해 토글을 몇 번 해야하는지 계산해 반환한다.

 

isOn 배열을 초기화하고, x를 xVec으로 변환한 후 반복문을 1부터 n까지 돌면서 문제를 풀기 시작한다. i가 x와 같다면 굳이 계산하지 않아도 돼서 빼줬다. i를 iVec으로 변환한 후, xVec[j]를 iVec[j]로 변환하는 데 드는 카운팅을 모두 계산해 diff에 더했다. 그리고 diff가 p 이하면 바꿀 수 있는 것으로 판단해 result++을 해줬다.

 

문제는 되게 쉬운데 풀이가 너무 귀찮다. 이를 더 쉽게 하는 방법이 없을까 ?