백준 - 22251 빌런 호석

문제

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

22251번: 빌런 호석

치르보기 빌딩의 엘리베이터 디스플레이의 숫자를 변경할 수 있는 경우의 수를 계산하는 문제였다.

아래는 각각의 숫자가 보이는 방식이다.

 

 

문제 풀이

0~9까지의 숫자들의 7개의 표시등을 모두 저장하고 각각의 숫자가 다른 숫자로 바뀔 때 필요한 반전 횟수를 계산해 저장했다. 그리고 숫자를 변경할 때 K자리의 LED이기 때문에 12라는 숫자를 0012라고 표기해야 하기 때문에 string 으로 변환해준 후, 백트래킹을 하며 앞자리부터 계속해서 바꿔줬다. 

 

처음에 아무리 생각해도 로직상 되어야 하는데 계속 틀렸다고 하길래 종료 조건을 바꿨더니 바로 해결됐다. 항상 종료 조건을 잘 살펴야겠다. 휴~

//0~9까지 led 등
int num[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} };

//i -> j 바꾸는데 필요한 반전 횟수
int changeCost[10][10];
int N, K, P, X;
string numStr;
int answer = 0;
set<int> numSet;

int calCost(int a, int b) { //a를 b로 바꾸는 데 필요한 반전 횟수 계산
    int cnt = 0;
    for (int i = 0; i < 7; i++) {
        if (num[a][i] != num[b][i]) cnt++;
    }
    return cnt;
}

void initCost() {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            changeCost[i][j] = calCost(i, j);
            //printf("cost %d to %d : %d\n", i, j, changeCost[i][j]);
        }
    }
}

string changeIntToString() { //X를 K자리의 string으로 바꾸기
    string s = to_string(X);
    while (s.length() < K) {
        s.insert(s.begin(), '0');
    }
    return s;
}

//변경할 자리 위치, 남은 변경 가능 횟수
void findMinCnt(int index, int remainCnt) {

    if (index >= K) {
        int nowMakeNum = stoi(numStr);
        if (nowMakeNum <= N && nowMakeNum > 0 && nowMakeNum != X) {
            answer++;
        }
        return;
    }

    //변경할 자리의 원래 숫자
    int nowNum = numStr[index] - '0';

    for (int i = 0; i < 10; i++) { //0~9까지 변경 가능한 숫자 변경, 자기 자신이면 변경하지 않는 것    
        int cost = changeCost[nowNum][i];
        //printf("nowNum: %d i: %d cost: %d remainCost: %d\n", nowNum, i, cost, remainCnt);        
        if (remainCnt >= cost) { //변경 가능
            numStr[index] = i + '0';
            findMinCnt(index + 1, remainCnt - cost);
            numStr[index] = nowNum + '0';
        }
    }
}

int main(int argc, char** argv)
{
    scanf("%d %d %d %d", &N, &K, &P, &X);

    numStr = changeIntToString();
    initCost();

    findMinCnt(0, P);

    printf("%d", answer);
    return 0;
}

 

아래는 안 되던 코드의 문제 부분이다.

void findMinCnt(int index, int remainCnt) {

    int nowMakeNum = stoi(numStr);
    if (nowMakeNum <= 0 || nowMakeNum > N || index > K || remainCnt < 0) return;

    if (index == K) {
        if (numSet.count(nowMakeNum) == 0 && nowMakeNum != X && nowMakeNum != 0) {
            numSet.insert(nowMakeNum);
            //cout << numStr<<endl;
            answer++;
        }
        return;
    }

    //변경할 자리의 원래 숫자
    int nowNum = numStr[index] - '0';

    for (int i = 0; i < 10; i++) { //0~9까지 변경 가능한 숫자 변경, 자기 자신이면 변경하지 않는 것    
        int cost = changeCost[nowNum][i];
        //printf("nowNum: %d i: %d cost: %d remainCost: %d\n", nowNum, i, cost, remainCnt);
        if (remainCnt >= cost) { //변경 가능
            numStr[index] = i + '0';
            findMinCnt(index + 1, remainCnt - cost);
            numStr[index] = nowNum + '0';
        }
    }
}