백준 4375 - 1 (모듈러 연산)

문제 : 4375번: 1 (acmicpc.net)

4375번: 1

 

풀이과정

1, 11, 111, 1111 ...

이렇게 자리수가 하나씩 늘어난다고 할 때 입력값 n의 배수인 가장 작은 수의 자리수를 구하는 문제였습니다.

ex) 답이 1111이라면 4 출력

 

한자리씩 계속해서 늘려가면서 답을 비교해보면 좋겠지만 무한히 늘어난다면 int형으로 담을 수 없기 때문에

모듈러 연산을 통해 풀이할 수 있었습니다.

풀이의 주석을 참고해주세요

 

#include <iostream>
#include <vector>
#include <stdio.h>
#include <string>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;

int main() {
    int n;
    while (cin >> n) {
        int num = 0;
        int cnt = 0;
        while(1) {
            // 자리수 추가
            num = num*10 +1;
            // 모듈러 연산을 통해 무한히 커지는걸 방지
            num %= n;
            cnt++;
            if(num == 0) {
                printf("%d\n",cnt);
                break;
            }
        }
    }
}