[백준 4375] 1

문제

4375번: 1

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

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

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

풀이

공유 소스 보기

아이디어

• 1 부터 cnt 까지 n 으로 계속 나누는 것은 cnt 의 시간 복잡도가 발생해 시간 초과가 발생한다.
  • 최대 입력값인 9999 을 1 부터 cnt 까지 계속 나누다 보면 int 혹은 long long 자료형의 범위를 벗어나는 것을 확인할 수 있다.
• 이를 해결하기 위해서는 cnt 를 계속 n 으로 나누는 것이 아니라 현재 cnt 의 이전 나머지 값을 n 으로 나누면 해결할 수 있다.
  • 즉, 분모가 되는 기준값은 (cnt % n) * 10 + 1 이 된다.
  • 이와 같이 이전 기준값의 나머지를 n 으로 나누는 방식을 이용할 경우 n 의 배수가 int 나 long long 의 범위를 넘어서는 경우에도 계산이 가능하다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int n;

int main() {
    while (scanf("%d", &n) != EOF) {
        ll cnt = 1L, r = 1L;
        while (cnt % n != 0) {
            cnt = (cnt % n) * 10 + 1;
            r++;
        }
        cout << r << "\n";
    }
    return 0;
}