문제
민석이는 불면증에 걸렸다. 그래서 잠이 안 올 때의 민간요법 중 하나인 양 세기를 하려고 한다.
민석이는 1번 양부터 순서대로 세는 것이 재미없을 것 같아서 N의 배수 번호인 양을 세기로 하였다.
즉, 첫 번째에는 N번 양을 세고, 두 번째에는 2N번 양, … , k번째에는 kN번 양을 센다.
이렇게 숫자를 세던 민석이에게 잠은 더 오지 않고 다음과 같은 궁금증이 생겼다.
이전에 셌던 번호들의 각 자리수에서 0에서 9까지의 모든 숫자를 보는 것은 최소 몇 번 양을 센 시점일까?
예를 들어 N = 1295이라고 하자.
첫 번째로 N = 1295번 양을 센다. 현재 본 숫자는 1, 2, 5, 9이다.
두 번째로 2N = 2590번 양을 센다. 현재 본 숫자는 0, 2, 5, 9이다.
현재까지 본 숫자는 0, 1, 2, 5, 9이다.
세 번째로 3N = 3885번 양을 센다. 현재 본 숫자는 3, 5, 8이다.
현재까지 본 숫자는 0, 1, 2, 3, 5, 8, 9이다.
네 번째로 4N = 5180번 양을 센다. 현재 본 숫자는 0, 1, 5, 8이다.
현재까지 본 숫자는 0, 1, 2, 3, 5, 8, 9이다.
다섯 번째로 5N = 6475번 양을 센다. 현재 본 숫자는 4, 5, 6, 7이다.
현재까지 본 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9이다.
5N번 양을 세면 0에서 9까지 모든 숫자를 보게 되므로 민석이는 양 세기를 멈춘다.
[입력]
첫 번째 줄에 테스트 케이스의 수 TC가 주어진다.
이후 TC개의 테스트 케이스가 새 줄로 구분되어 주어진다.
각 테스트 케이스는 다음과 같이 구성되었다.
첫 번째 줄에 정수 N, M이 주어진다. (1 ≤ N ≤ 30 , 0 ≤ M ≤ 108)
[출력]
각 테스트 케이스마다 한 줄씩
마지막 N개의 비트가 모두 켜져 있다면 ON
아니면 OFF 를 출력하라.
#include <iostream>
using namespace std;
int main()
{
int test_case,n,s_n,mul,flag=0;
cin >> test_case;
for (int i = 0; i < test_case; i++)
{
cin >> n;
mul = 0;
while (1)
{
mul += n;
s_n = mul;
while (s_n > 0)
{
flag |= (1 << s_n % 10);
s_n = s_n / 10;
}
if (flag == (1 << 10) - 1)
{
cout << "#" << i + 1 << " " << mul << endl;
flag = 0;
break;
}
}
}
return 0;
}
비트연산을 이용하여 간단하게 구현할 수 있었다.
mul 변수에 반복문 횟수만큼의 N을 저장한다. 즉 X번 째의 N의 값을 저장
s_n에 mul을 복사하여 N, 2N, 3N ..... XN의 값을 저장한다.
s_n의 일의 자리 수부터 구하여 값을 flag에 누적시킨다.
그리고 s_n을 10으로 나눈 몫을 저장하여 자리수를 하나씩 내려준다. ex) 123 -> 12
이 과정을 반복하여 flag에 s_n의 각 자릿수들을 누적시켜 저장하는데
0~9까지의 자릿수가 모두 누적이 된다면 flag는 0~9까지의 비트 값이 모두 1로 된다.
비트 연산에 의하면 2^(n) - 1 = 2^(n-1) + 2^(n-2) + ...... 2^(0) 이므로
flag == (2^10 - 1) 인 경우 문제의 조건을 만족한다.
비트연산을 이용하면 매우 간단하게 풀 수 있는 문제들이 종종 보인다.
<< >> 시프트 연산과 |= &=로 교집합 합집합 개념을 잘 이해하고 넘어가야겠다.
(문제 다 포스팅하려면 시간이 좀 걸릴거 같다...)