BOJ: 빌런 호석(22251) [C++]
치르보기 빌딩은 1층부터 𝑁층까지 이용이 가능한 엘리베이터가 있다. 엘리베이터의 층수를 보여주는 디스플레이에는 𝐾 자리의 수가 보인다. 수는 0으로 시작할 수도 있다. 0부터 9까지의 각 숫자가 디스플레이에 보이는 방식은 아래와 같다. 각 숫자는 7개의 표시등 중의 일부에 불이 들어오면서 표현된다.
빌런 호석은 치르보기 빌딩의 엘리베이터 디스플레이의 LED 중에서 최소 1개, 최대 𝑃개를 반전시킬 계획을 세우고 있다. 반전이란 켜진 부분은 끄고, 꺼진 부분은 켜는 것을 의미한다. 예를 들어 숫자 1을 2로 바꾸려면 총 5개의 LED를 반전시켜야 한다. 또한 반전 이후에 디스플레이에 올바른 수가 보여지면서 1이상 𝑁이하가 되도록 바꿔서 사람들을 헷갈리게 할 예정이다. 치르보기를 사랑하는 모임의 회원인 당신은 호석 빌런의 행동을 미리 파악해서 혼쭐을 내주고자 한다. 현재 엘리베이터가 실제로는 𝑋층에 멈춰있을 때, 호석이가 반전시킬 LED를 고를 수 있는 경우의 수를 계산해보자.
입력
𝑁,𝐾,𝑃,𝑋가 공백으로 구분되어 첫째 줄에 주어진다.
출력
호석 빌런이 엘리베이터 LED를 올바르게 반전시킬 수 있는 경우의 수를 계산해보자.
n: 최대 층수
k: 자리수
p: 반전시킬 led 최대 개수
x: 실제 층수
디지털시계 형식으로 숫자를 나타낸다면 각 획? 의 켜짐/꺼짐 여부로 어떤 숫자인지 알 수 있을 것
불 켜짐/꺼짐 여부를 가지고 숫자를 이진수로 나타낸 뒤, 반전할 수 있는 즉 서로 다른 비트의 개수가 몇개인지 세는 작업이 필요하다.
서로 다른 비트 개수가 1개 이상 p개 이하라면 조건을 만족한다.
먼저 숫자를 비트로 표현해주자
vector<int> bit_number = {0b1111110, 0b0110000, 0b1101101, 0b1111001, 0b0110011, 0b1011011, 0b1011111, 0b1110000, 0b1111111, 0b1111011};
서로 다른 비트를 확인할 때 xor 연산을 사용할 수 있다
xor은 두 비트가 같으면 0, 다르면 1이 나오니까 xor 연산을 통해 비트가 다른 부분만 1을 남긴다.
이때 1의 개수가 곧 반전할 수 있는 비트이므로 이것을 세어준다.
비트연산에서 1의 개수는 1과의 and 연산으로 세어줄 수 있다.
int calcDiff(vector<int>& start_num, int n, int k){ //x와 n의 서로 다른 비트수 계산
int cnt = 0;
for(int i=0;i<k;i++){ //n의 각 자리수
unsigned int diff = (start_num[i] ^ bit_number[n % 10]); //서로 다른 비트만 1로
for(int j=0;j<7;j++){ //서로다른 비트 개수세기
cnt += (diff & 1); //1과 and 연산
diff >>= 1; //shift
}
n /= 10; //다음 자리수로
}
return cnt;
}
위 함수를 이용해 1층부터 N층까지 탐색하며 조건( 서로 다른 비트 개수가 1개 이상 p개 이하 )에 맞는 경우를 세어준다.
전체 코드
#include <iostream>
#include <vector>
using namespace std;
vector<int> bit_number = {0b1111110, 0b0110000, 0b1101101, 0b1111001, 0b0110011, 0b1011011, 0b1011111, 0b1110000, 0b1111111, 0b1111011};
int calcDiff(vector<int>& start_num, int n, int k){ //x와 n의 서로 다른 비트수 계산
int cnt = 0;
for(int i=0;i<k;i++){ //n의 각 자리수
unsigned int diff = (start_num[i] ^ bit_number[n % 10]); //서로 다른 비트만 1로
for(int j=0;j<7;j++){ //서로다른 비트 개수세기
cnt += (diff & 1); //1과 and 연산
diff >>= 1; //shift
}
n /= 10; //다음 자리수로
}
return cnt;
}
int solution(int n,int k, int p, int x){
vector<int> start_num(k);
int tmp_x = x;
for(int i=0;i<k;i++){ //start_num에 현재층 각 자리수에 해당하는 비트값 저장
start_num[i] = bit_number[tmp_x % 10];
tmp_x /= 10;
}
int ans = 0;
for(int i=1;i<=n;i++){ //1층부터 n층까지 탐색
if (i==x) continue; //1개 이상 반전해야 하니까 같은 경우는 해당 X
int diff = calcDiff(start_num, i, k); //현재층 기준 서로다른 비트수 세기
if(diff>=1 && diff<=p) ans++; //반전 가능한 비트수가 1~p개라면 조건 만족
}
return ans;
}
int main()
{
int n,k,p,x;
cin>>n>>k>>p>>x;
cout << solution(n,k,p,x);
return 0;
}