백준 4375번 1 C++

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

각 자릿수가 모두 1로만 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

예제 입력 1 복사

3
7
9901

예제 출력 1 복사

3
6
12

 

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


int main()
{
	std::ios::sync_with_stdio(false);
	int n;  //입력
	
	
	
	while (cin >> n) {  //지수
		int  multi = 1;  //1로만 이루어진 의 배수
		int k = 1;
		while (1) {
			
			if (multi % n == 0)
			{
				
				break;
			}
			multi = multi * 10 + 1;
			multi %= n;
			k++;
		}
		cout << k << "\n";
	}
		

	
	return 0;
}

 

수학적으로 접근하여야 했다. 그냥 생각나는대로 접근한다면 

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


int main()
{
	std::ios::sync_with_stdio(false);
	int n;  //입력
	
	
	
	while (cin >> n) {
		int i = 0;  //지수
		int  multi = 1;  //1로만 이루어진 의 배수
		while (1) {
			multi = multi * 10 + 1;
			if (multi % n == 0)
			{
				cout << i + 1 <<"\n";
				break;
			}
			i++;
		}
		
	}
		

	
	return 0;
}

이런식으로 짯었는데 이렇게 계산하면 숫자가 커지면 커질수록 자릿수가 늘어나 주어진 자료형으로는 한계가 있다. 
따라서 모듈러 연산을 통하여 숫자를 줄이면서 계산을 할 수 있다.

 

모듈러 연산은 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의 하는 방법이다.

 

예시)

8 mod 4= ?

모듈이 4이므로 숫자 0, 1, 2, 3이 있는 시계를 만듭니다.
0에서 시작하여 8까지 시계 방향으로 1, 2, 3, 0, 1, 2, 3, 0과 같이 움직입니다.

0에서 멈추기 때문에 8 mod 4= 0

 

x mod N = (x mod N) mod N 

 

이므로 이를 이용하여 코드를 수정하였다.

 

 

ref . https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic