[백준] 4375 1

[백준] 4375 1

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

• 아무런 처리 없이 1로만 이루어진 수(oneNum)를 만드는 경우
  -> unsigned long long의 범위에서 벗어날 수 있음
  -> 33%에서 시간 초과

• n의 배수를 찾는 while문 내에서 모듈라 연산을 이용하여 oneNum의 크기를 줄여야 함
  -> x mod N = (x mod N) mod N

#include <iostream>
#include <algorithm>
using namespace std;

typedef unsigned long long ull;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	//EOF를 만날때까지 무한 입력
	while (true) {
		ull n;
		cin >> n;
		if (cin.eof() == true) break;
		
		//1로 이루어진 수
		ull oneNum = 1LL;
		//1로 이루어진 수의 1의 수
		int cnt = 1;

		while (oneNum < n) {
			oneNum *= 10;
			oneNum++;
			cnt++;
		}

		while (true) {
			//n의 배수가 아닐 경우
			if (oneNum % n) {
				//다음 1로 이루어진 수 만들기
				oneNum *= 10;
				oneNum++;
				cnt++;
                //oneNum 너무 커지는 것 방지용 모듈라 연산
				oneNum %= n;
			}
			else {
				break;
			}
		}
		cout <<cnt<< "\n";
	}

	return 0;
}

📌참고자료

• [C++] 백준 4375번 - 1 (시간초과, Modular 연산 활용)
  https://nanyoungkim.tistory.com/115