백준 22251번 빌런 호석 (C++)

문제 링크 : https://www.acmicpc.net/problem/22251

22251번: 빌런 호석

문제 요약

디스플레이 LED

1. 빌딩의 엘리베이터는 1층부터 N층까지 이용가능합니다.

2. 현재 층은 X층입니다.

3. 엘리베이터에서는 K자리수로 층이 보여집니다. (ex : K=4, X=1 -> 0001)

4. 호석이는 엘리베이터 디스플레이 중에서 최소 1개, 최대 P개를 반전시켜 층을 혼선시킬 예정입니다.

디스플레이를 반전시켜도 1이상 N이하의 층만 표시가 가능하빈다.

5. 현재 층 X에서 호석이가 반전시켜 나타낼 수 있는 층의 갯수를 구하세요.

 

핵심 포인트

 

호석이는 최대 P개의 디스플레이를 반전시킬 수 있습니다.

예를들어 현재 층이 1001일 경우, 2개의 디스플레이를 반전시켜 7007로 표시할 수 있습니다.

 

문제 풀이

 

1. 필요한 변수를 선언하고 값을 입력받습니다.

// 전역변수
int n,k,p,x; // n=1층부터 n층, k=최대 k자리수가 보여짐, p=최대 p개 반전, x=현재 있는 층
bool ch[10][7] = { {true,true,true,false,true,true,true}, // 0
                   {false,false,true,false,false,false,true}, // 1
                   {false,true,true,true,true,true,false}, // 2
                   {false,true,true,true,false,true,true}, // 3
                   {true,false,true,true,false,false,true}, // 4
                   {true,true,false,true,false,true,true}, // 5
                   {true,true,false,true,true,true,true}, // 6
                   {false,true,true,false,false,false,true}, // 7
                   {true,true,true,true,true,true,true}, // 8
                   {true,true,true,true,false,true,true} // 9
                };
                
// 이하 int main()함수

cin >> n >> k >> p >> x;

위의 ch 배열은 0부터 9까지 디스플레이 표기를 나타낸 배열입니다. 표기를 나타낸 순서는 다음과 같습니다.

 

2. int change()함수를 활용해 1층부터 N층까지 디스플레이를 바꾸어 나타낼 수 있는 층의 갯수를 구합니다.

 int change(){ // k개 보여지고, p개까지만 바꿀 수 있으며, 현재 층은 x층
    int res = 0;
    for(int i=1; i<=n; i++){ // 1
        if(i==x) continue; // 2
        int cnt = 0; // 3
        int from = x,to = i; // 4
        for(int j=0; j<k; j++){ // 5
            for(int z=0; z<7; z++){ // 6
                if(ch[from%10][z]!=ch[to%10][z]) cnt++; // 7
            }
            from/=10; // 8
            to/=10;
        }
        if(cnt<=p) res++; // 9
    }
    return res; // 10
}

// int main() 내부
 	cout << change() << "\n";

(1) 1층부터 N층까지 디스플레이를 바꾸어 나타낼 수 있는 층을 파악합니다.

(2) 만약 i가 현재 층 x와 같을 경우, 판단할 필요가 없으므로 continue를 합니다.

(3) cnt는 i층을 표현하기 위해 바꾼 디스플레이의 갯수를 뜻합니다.

(4) 편의상 현재 층 x는 from, 목표층 i는 to로 표현합니다. 

(5) 0부터 k까지 for문을 돌립니다. 디스플레이에는 K자리수까지 보여지기 때문에, 0자리수부터 K자리수까지 from과 to가 일치하지 않는지, 일치하지 않을 경우 몇 개의 디스플레이를 바꿔야하는지 횟수를 셉니다.

(6) 0부터 7까지 for문을 돌립니다. 숫자 하나당 디스플레이 7개중 몇 개를 바꿔야하는지 세어줍니다.

(7) from%10과 to%10의 디스플레이가 몇 개나 다른지를 세어줍니다. %10과정을 통해 우리는 0자리부터 K자리까지 숫자의 디스플레이를 비교할 수 있습니다.

(8) 첫 째자리 디스플레이를 비교했으면 두 번째 자리 디스플레이를 비교하기 위해, from과 to는 각각 나누기 10을해줍니다.

이 과정을 K번이 될때까지 진행해줍니다.

(9) 그렇게 해서 변경된 디스플레이 수(=cnt)가 p이하일 경우, res를 +1해줍니다.

(10) res를 결과로 반환합니다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int n,k,p,x; // n=1층부터 n층, k=최대 k자리수가 보여짐, p=최대 p개 반전, x=현재 있는 층
bool ch[10][7] = { {true,true,true,false,true,true,true}, // 0
                   {false,false,true,false,false,false,true}, // 1
                   {false,true,true,true,true,true,false}, // 2
                   {false,true,true,true,false,true,true}, // 3
                   {true,false,true,true,false,false,true}, // 4
                   {true,true,false,true,false,true,true}, // 5
                   {true,true,false,true,true,true,true}, // 6
                   {false,true,true,false,false,false,true}, // 7
                   {true,true,true,true,true,true,true}, // 8
                   {true,true,true,true,false,true,true} // 9
                };

int change(){ // k개 보여지고, p개까지만 바꿀 수 있으며, 현재 층은 x층
    int res = 0;
    for(int i=1; i<=n; i++){
        if(i==x) continue;
        int cnt = 0;
        int from = x,to = i;
        for(int j=0; j<k; j++){
            for(int z=0; z<7; z++){
                if(ch[from%10][z]!=ch[to%10][z]) cnt++;
            }
            from/=10;
            to/=10;
        }
        if(cnt<=p) res++;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> k >> p >> x;
    cout << change() << "\n";
    return 0;
}