<백준 4375번> 1

문제

---

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

 

입력

---

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

 

출력

---

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

 

 

예제 입력 1

---

3
7
9901

 

예제 출력 1

---

3
6
12

 

 

문제 분석

---

이 문제는 나머지 연산의 원리를 알아야 시간초과가 안나고 풀 수 있다.

만약 1부터 11111...1111까지를 대입해서 풀다보면 당연히 시간초과가 날 수 밖에 없다.

 

나머지 연산은 다음과 같다. 

'(A+B)%C와 (A%C + B%C)%C는 같다'

 

위 공식을 해당 문제에 대입하여 풀 경우,

1. N=7

2. 11= (1*10+1)%7

3. ((1%7)*10+1)%7 = 11%7 = 4

4. 111 = (11*10+1)%7

5. (11%7)*10+1 = 40+1 =41%7 = 6

이라는 공식이 성립된다.

 

 

코드

---

#include<bits/stdc++.h> 
using namespace std;
typedef long long ll;
int n;

int main() {
    while(scanf("%d", &n) != EOF)
    {
    	int cnt = 1, ret = 1;
    	while(true)
    	{
    		if(cnt % n == 0)
    		{
    			printf("%d\n", ret);
    			break;
			}
			else
			{
				cnt = (cnt * 10) + 1;
				cnt %= n;
				ret++;
			}
		}
	}
    return 0;
}

 

 

문제 분석 출처 : https://astrid-dm.tistory.com/299

#4375번 1 (C++)