[코드업] 2102 - 배수(hard)

입력 예시   

3

출력 예시

111

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

unsigned long long N;

// 2^64는 10^20보다 작다.
// 따라서 1또는 0으로 만들 수 있는 최대의 수는 1을 20번쓰는 것이다..
const unsigned long long limit = 11111111111111111111;							     
unsigned long long minValue = UINT64_MAX;

void solve(unsigned long long start){
	if (start % N == 0) 
		minValue = min(minValue, start);

	if (start > limit / 10) 
		return;
	solve(start * 10 + 1);
	solve(start * 10);
}
int main(){
	cin >> N;

	if (N > limit) {
		printf("0");
		return 0;
	}

	solve(1);

	if (minValue == UINT64_MAX)
		cout << 0;
	else cout << minValue;
	return 0;

}