백준 4375 : 1. 모듈러 연산 2

2023.08.31 - [알고리즘/백준] - 백준 1629 곱셈 , 모듈러 연산 , 재귀함수

백준 1629 곱셈 , 모듈러 연산 , 재귀함수

모듈러 연산에 대한 기초 내용을 저번 포스트에서 다뤘는데요. 이번에는 더 심화로 백준 4375를 풀어보겠습니다.

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

4375번: 1

 

코드를 설명하기 전에, 문제의 핵심 아이디어를 먼저 이해해야 합니다. 문제에서 우리는 모든 자리수가 1로만 이루어진 n의 배수를 찾아야 합니다. 예를 들어 n이 3이면, 이러한 배수 중 가장 작은 것은 111입니다.

1. 입력 n을 받습니다.

2. while 루프를 사용하여 n의 배수를 찾을때까지 계속하여 1을 추가하며 숫자를 증가시킵니다.

3. if(ret%n == 0) 을 통해 현재숫자가 n의 배수인지 확인합니다.

4. 배수라면, cnt 를 출력하고 루프를 종료합니다.

5 . ret = (ret * 10) + 1;
이 연산은 현재의 수(모든 자릿수가 1인 수)에 10을 곱하여 하나의 0을 추가하고,

그런 다음 1을 더하여 새로운 1로 끝나는 수를 만드는 것입니다. 예를 들어, ret이 11이면 이 연산 후에 ret은 111이 됩니다.

그런 다음 코드에서는:
ret %= n;
이 연산을 수행하여 ret을 n으로 나눈 나머지를 저장합니다.

이것이 왜 중요한지에 대한 예제를 살펴보겠습니다.

n이 7이고 ret이 111일 때, (111 * 10 + 1) % 7을 계산하려고 한다고 가정해보겠습니다.

1111을 직접 계산하고 7로 나누는 대신 두 단계로 나눠서 계산할 수 있습니다.

{(111 % 7) * (10%7)} % 7  = (6*3) % 7 = 4
(4 + 1) % 7 = 5
따라서 (111 * 10 + 1) % 7의 결과는 5입니다.

이 방식을 사용하면 큰 수를 직접 다루지 않고도 모듈러 연산을 수행할 수 있습니다. 

6.cnt 를 1씩 증가시킨다. 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main ()
{   int n;
  
    while(scanf("%d",&n)!=EOF)
    {
        int cnt=1, ret=1;
        while(1)
        {
            if(ret % n ==0)
            {
                cout << cnt<<"\n";
                break;
            }
        else {
            ret= (ret*10)+1;
            ret%=n;
            cnt ++;
            }
            
        }
    }
}