[백준 4375] 1 (C#, C++) - soo:bak

문제 링크

4375번 - 1

설명

2와 5로 나누어떨어지지 않는 정수 n (1 ≤ n ≤ 10,000)이 여러 개 주어지는 상황에서, 각 n에 대해 모든 자릿수가 1로만 이루어진 n의 배수 중 가장 작은 수의 자릿수 개수를 구하는 문제입니다.

입력은 EOF까지 주어집니다.

접근법

모든 자릿수가 1인 수는 1, 11, 111, 1111, … 형태입니다.

이러한 수 중에서 n의 배수가 되는 가장 작은 수의 자릿수를 찾아야 합니다.

직접 1, 11, 111, 1111, …을 만들어 n으로 나누면 수가 너무 커져서 오버플로우가 발생합니다.

따라서, 나머지 연산의 성질을 이용하여 나머지만 추적합니다.

k자리 수 111…1을 n으로 나눈 나머지를 알고 있을 때, k+1자리 수 111…11은 다음과 같이 표현할 수 있습니다.

111…11 = 111…1 × 10 + 1

즉, k+1자리 수의 나머지는 (이전 나머지 × 10 + 1) % n으로 계산할 수 있습니다.

예를 들어 n = 3일 때:

• 1자리: 1 % 3 = 1
• 2자리: (1 × 10 + 1) % 3 = 11 % 3 = 2
• 3자리: (2 × 10 + 1) % 3 = 21 % 3 = 0

나머지가 0이 되므로 111은 3의 배수이고, 답은 3입니다.

길이를 1부터 시작하여 나머지가 0이 될 때까지 반복하며 자릿수를 증가시킵니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      string? line;

      while ((line = Console.ReadLine()) != null) {
        var n = int.Parse(line);
        var len = 1;
        var rem = 1 % n;

        while (rem != 0) {
          rem = (rem * 10 + 1) % n;
          len++;
        }

        Console.WriteLine(len);
      }
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  while (cin >> n) {
    int len = 1;
    int rem = 1 % n;

    while (rem != 0) {
      rem = (rem * 10 + 1) % n;
      len++;
    }

    cout << len << "\n";
  }

  return 0;
}