본문 바로가기
🥇Baekjoon Solutions/정수론

[C++] 백준 4375번: 1

by 코푸는 개발자 2021. 7. 27.
728x90

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

 

4375번: 1

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

www.acmicpc.net

최초 오류

무작정 11...11인 수를 n으로 나누려한다면 런타임 에러가 발생한다.
이유: 계속 안나눠 진다면 11...11의 길이가 무한정 커져서 계산 자체에 오류가 발생한다.

길이(자리수)가 2000이라면 계산이 될 수 없기 때문이다.

 

풀이

문제에서 어떤 수로 나누어진다는 것을 판별 할때는 커지는 수를 계속해서 나누려는 수로 나눈나머지로 한정시켜킨다.

(a+b)%c = (a%c+b%c)%c (나머지는 같음을 이용함 계속해서 나머지만을 이용)

작은 자리숫자 중 나누어진 것은 더 이상 계산할 필요가 없다.

#include <iostream>

using namespace std;

void solve(int n) {
	int count = 0, num = 0;
	while (true) {
		num = (num * 10 + 1)%n;
		count++;
		if (num == 0) break;
	}
	cout << count << endl;
}

int main() {
	int n;
	while(cin>>n)// 테스트 케이스 제한이 없다면
		solve(n);

	return 0;
}

*자리수가 엄청긴 숫자는 문자열로 받아 나누기를 진행할 때 작은 자리부터 나누려는 수로 나누어 나머지만을 계산

728x90

댓글