BOJ-1612-가지고 노는 1

필요한 지식

1. 수학

접근

• n의 배수중 1로만 이루어진 수중 가장 작은 자릿수를 출력해야한다. 없다면 -1을 출력한다.

• 불가능한 경우는 1로만 이루어진 수는 약수로 2와5를 가지고있지 않다. 그러므로 n을 입력받을 때에 2나5로 나누어떨어진다면 -1을 출력해준다.

• 1로만 이루어진 배수를 구해줄 때에, 1111을 확인 후 *10+1을 해서 11111을 만들어가며 계산한다면 1로만 이루어진 배수의 크기가 너무 커진다.

• 1로만 이루어진 배수를 저장하는 변수를 계속 n으로 모듈러 연산을 해주며 숫자가 너무 커지지 않게한다.

• 모듈러 연산으로 수를 커지지않게 하는 방법은 동적계획법에서 많이 사용하던 방법인데도 불구하고 떠올리기가 많이 오래 걸렸다..

코드(C++)

#include <iostream>
using namespace std;
int main() {
	int n, ans = 1, tmp = 1; cin >> n;
	if (n % 2 == 0 || n % 5 == 0) {
		cout << "-1" << "\n";
		return 0;
	}
	while ((tmp % n) != 0) {
		ans += 1;
		tmp = (tmp % n) * 10 + 1;
	}
	cout << ans << "\n";
	return 0;
}

결과