[C++]/백준 4375번 1

• 문제

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

• 입력

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

• 출력

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

• 예제 입력

3
7
9901

• 예제 출력

3
6
12

• 접근방식

1, 11, 111 ...을 % n == 0 이면 배수임 → 1의 개수를 카운팅 → 수가 너무 크면 오버 플로우 발생

따라서 모듈러 산술 연산을 이용해야함

모듈러 산술 연산은 분배 법칙이 성립함

11 = 10 +1 이고 111 = 100 + 10 + 1 ... 이런식으로 나아간다

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;

int main() 
{
	while (cin >> n)
	{
		int cnt = 1, ret = 1; // ret은 1의 갯수

		while (1)
		{
			if (cnt % n == 0) // cnt가 n의 배수이면 종료
			{
				cout << ret << "\n";
				break;
			}
			else
			{
				cnt = (cnt * 10) + 1; // (cnt *10) + 1 을 반복하면 111 = 100+10+1 처럼 만들수 있음
				cnt %= n; // 모듈러 연산으로 오버플로우 방지
				ret++;
			}
		}
	}

	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/4375

4375번: 1