백준 빌런 호석 22251

문제 설명

• 1층부터 N층까지 이용할 수 있는 엘리베이터가 있다.
• 엘리베이터 층수는 총 K자리까지 보여지는데 각 자리는 총 7개의 표시등으로 나타낸다.
• 여기서 P개의 라이트를 반전시켜서 층수를 변경할 수 있는데 현재 X층이라고 할 때 총 몇개의 층으로 변경할 수 있는지 구해라.

문제 링크

문제 접근

• 원래는 각 숫자별로 몇개를 변경해야 해당 숫자가 될 수 있는지 2차원 배열로 하나하나 구할 생각이었다.
• 위 방법은 시간도 오래 걸리고 정확도도 떨어질 가능성이 있어서 7개의 표시등에 번호를 매겨서 각 숫자별로 배열을 만들어 저장해뒀다.
• 이후 배열을 순화하며 몇 개를 변경해야 하는지를 숫자별로 2차원 배열에 저장해둔다.
• 이후 재귀를 돌면서 각 자리별로 바꿔야하는 라이트 수와 현재 바꿀 수 있는 라이트 수를 비교하며 조건에 맞게 재귀를 돌렸다.

문제 코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int    diff[10][10];
int ret = 0;
int display, now;
int limit;
int ele[10000000];

void    solv(int check,  int t_now, int upside, int num)
{
    int    calc = t_now % 10;

    t_now /= 10;
    if (check == display && upside >= 0)
    {
        if (ele[num] == 0 && num <= limit &&  num != now)
        {
            ele[num] = 1;
        }
        return;
    }
    for (int i = 0; i <= 9; i++)
    {
        if (diff[calc][i] <= upside)
        {
            solv(check + 1, t_now, upside - diff[calc][i], num + i * pow(10, check));
        }
    }
}

int main()
{
    int upside;
    bool flag = true;
    int    led[10][7] = {{1, 1, 1, 0, 1, 1, 1}, \
                    {0, 0, 1, 0, 0, 1, 0}, \
                    {1, 0, 1, 1, 1, 0, 1}, \
                    {1, 0, 1, 1, 0, 1, 1}, \
                    {0, 1, 1, 1, 0, 1, 0}, \
                    {1, 1, 0, 1, 0, 1, 1}, \
                    {1, 1, 0, 1, 1, 1, 1}, \
                    {1, 0, 1, 0, 0, 1, 0}, \
                    {1, 1, 1, 1, 1, 1, 1}, \
                    {1, 1, 1, 1, 0, 1, 1}};


    cin>>limit>>display>>upside>>now;
    for (int i = 0; i < 10; i++)
    {
        for (int j = 0; j < 10; j++)
        {
            int count = 0;
            for (int k = 0; k < 7; k++)
            {
                if (led[i][k] != led[j][k])
                    count++;
            }
            if (i == j)
                count = 0;// ㅇㅕ기 때문에 한참을 헤맸다 -> 현재 숫자와 동일한 숫자는 할 수 없도록 1000으로 설정했었는데 한 자리만 다르면 다른 숫자이므로 이렇게 접근하면 안된다.
            diff[i][j] = count;
        }
    }
    solv(0, now, upside, 0);
    for (int i = 1; i <= limit; i++)
    {
        if (ele[i] == 1 && i != now)
        {
            ret++;
        }
    }
    cout<<ret<<endl;
}