백준 4375번 1

<백준 4375번 1 - 마포 코딩박>

사용한 알고리즘: 수학


입력되는 수 n 을 갖고 1, 11, 111, ... 등 1로만 이루어진 가장 작은 n의 배수를 찾는 문제입니다.
문제풀이는 다음과 같습니다.

(1) 기본 생각은 K=1을 시작으로 1, 11, 111, ... 차례로 K 자리수를 늘려 n으로 나누어보는 것입니다.

(2) 이때 자리수를 하나 올려줄때마다 기존의 K를 modulo n 을 취해줘야 시간내에 돌아갑니다.

예를들어 n = 3 이 주어지고 K = 11 이 나누어지지 않아 K = 111을 보는 경우를 생각하면,  11 = 9 + 2 = 2 (mod 3) 이므로 111 = 110 + 1 = 20 +1 = 21 (mod 3) 입니다.

	#include <bits/stdc++.h>
	using namespace std;
	#define ll long long
	int num;
	int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
	while(cin >> num){
	int cnt = 1;
	ll K = 1LL;
	while(1) {
	if(K%num==0){
	cout << cnt << '\n';
	break;
	}
	// 나눠 떨어지냐 아니냐가 중요.
	// 즉 num=3 일때, 11->111 가는 과정에서 110=90+20=20(mod 3)
	K%=num;
	K=(K*10)+1;
	cnt += 1;
	}
	}
	return 0;
	}

view raw BOJ 4375.cpp hosted with ❤ by GitHub