SWEA 1288. 새로운 불면증 치료법 (C++)

요약

배열이 아닌 비트로 표현한 수에, visited를 저장했다.

비트연산
| OR연산자, 둘 중 하나만 1이어도 1이 된다.
a << b a 를 왼쪽으로 b만큼 민다.

숫자를 나누어서 나머지 값들을 저장하는 것 대신, 숫자를 문자열로 바꾸었다.

to_string()
string 헤더를 필요로 함.

---

문제

첫 번째에는 N번 양을 세고, 두 번째에는 2N번 양, … , k번째에는 kN번 양을 센다.
이전에 셌던 번호들의 각 자리수에서 0에서 9까지의 모든 숫자를 보는 것은 몇 번 양을 센 시점일까?

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

[출력]
최소 몇 번 양을 세었을 때 이전에 봤던 숫자들의 자릿수에서 0에서 9까지의 모든 숫자를 보게 되는지 출력한다.

---

풀이

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

int N;
int cnt;
int visited;  // 현재까지 본 숫자들을 bit로 표현한 수
int total = (1 << 10) - 1; // 모든 숫자가 등장했을 때, visited

void init() {
	cin >> N;
}

bool calc(int cnt){

	// 숫자로 두면 일일이 나누고, 나머지를 기록해야하니, 문자열로 전환
	string x = to_string(N * cnt);
	for (int i = 0; i < x.length(); i++) {
		int num = x[i] - '0';
		visited = visited | (1 << num);
	}
	if (visited == total) return true;
	else return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();

	int T;
	cin >> T;
	for (int tc = 1; tc <= T; tc++) {

		init();
		cnt = 1;
		visited = 0;
		bool cmd = false;
		while (!cmd) {
			if (!calc(cnt)) cnt++;
			else cmd = true;
		}

		cout << "#" << tc << " " << cnt*N << "\n";
	}

	return 0;
}