[C++][백준] - 1 (4375번)

https://www.acmicpc.net/problem/4375

4375번: 1

🔔 문제 : 

 

1 <= n <= 10,000

 

2와 5로 나누어 떨어지지 않는 정수 n의 배수  == 1로 이루어진 정수 찾기

 

예를 들어 1, 11, 111, 1111 등인 숫자들이 n의 배수가 되는 최소값을 찾아서 자리수를 출력한다.

 

ex) 3 * 37 = 111 -> 3자리

 

---

🔔 Kick Point :

 

n : 입력값

m: 1로 이루어진 수이라고 할 때

 

순수하게 m값을 증가해 가며 조건을 찾으려는 경우에는 1의 값이 111111111111 .... 등등으로 자리수가 비대해지기 때문에 변수의 범위를 넘어서게 되고 시간초과가 났다. 

이를 해결하기 위해서 m %= n 한 나머지값에 *10 + 1 연산을 하여 m값을 키웠다.

 

예시로 11은   (1 * 10) + 1 이고 이를 N으로 나눈 나머지 값은

11 % N = ((1 % N) * 10 + 1 % N) % N 인 값과 같게 된다.

 

" (A+B) % C  == (A % C + B % C) % C "

" (A * B) % C  == (A % C * B) % C " 

 

---

🔔 Code :

 

#include <iostream>
using namespace std;

int main()
{
	int n; // 입력 n
	long long m; // 1로 이루어진 값 -> 1, 11, 111 ...
	int cnt; // 결과값, 자릿수
	
	
	while (cin >> n) {
		m = 1; cnt = 1;

		while (true) {
			
			if (m % n == 0) {
				cout << cnt << endl;
				break;
			}
			else {
				m %= n; // m의 수를 미리 mod 해줘서 속도를 높힌다.
				m = m * 10 + 1;
				cnt += 1;
			}
		
		}
	}
}

 

 

---