1

문제 푸는 방법

1. 최대 최소 확인

2. brute force가 가능한지 확인

3. 2번이 안된다면 다른 방법 생각

이번에도 또 1, 2, 3을 생각하지 않았다...

분석

문제를 푸는 로직은 1, 2 ,3 이다.

근데 해당로직대로 하면 overflow현상이 발생한다.

즉, 다른 방법을 생각해야한다.

moduler 연산 ❗

(a + b) % c는

(a % c + b % c) % c와 같기 때문에
(또는 a % c + b % c 와 같다.)

(3 * 3 * 3) % 2는

3 % 2 + 3 % 2 + 3 % 2 와 같다.

(3 % 2 + 3 % 2 + 3 % 2) % 2와 같다.

그러니까 3을 10번 곱하고 난뒤 % 2를 한 것과
(3 % 2) 를 10번 수행한것과 같다.

cpp 코드

#include <iostream>
#include <stack>
using namespace std;
#define endl "\n"
typedef long long ll;

int n;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	while (1)
	{
		int cnt = 1, ret = 1;
		cin >> n;
		if (cin.eof()) break;
		
		while (1)
		{
			if (cnt % n == 0)
			{
				cout << ret << endl;
				break;
			}
			else
			{
				cnt = (cnt * 10) + 1;
				cnt %= n;
				++ret;
			}
		}
	}
	
	return 0;
}