[C++] 백준(BOJ) - 4375 : 1

14 Jun 2023 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 알고리즘
• 풀이
• 코드
• 평가

문제

백준(BOJ) - 4375 : 1(링크)

알고리즘

1. 수학 - 모듈러 연산
2. 브루트포스

풀이

1. 1111….1 을 만들기 위한 점화식을 만들기

k = (k * 10) + 1; 

1. 중간 단계에서 모듈러 연산을 해도 전체를 구하고 나머지를 구하는 것과 값은 동일하다

모듈러 연산  
(a * b) % c = ((a % c) * (b % c)) % c  
(a + b) % c = ((a % c) + (b % c)) % c  

코드

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

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

    int a;
    while (cin >> a) // testcase 입력 별로 받기
    {
        if (a % 2 == 0 || a % 5 == 0) continue; // 문제의 선행 조건

        int cnt = 1;
        int k = 0;
        while (true)
        {
            k = (k * 10) + 1;
            k %= a; // 숫자가 너무 커질 경우 나머지만 가져간다
            if (k == 0) 
            {
                cout << cnt << '\n';
                break;
            }
            else cnt++;
        }
    }
    return 0;
}

평가

• 모듈러 연산 - (+, *) 이 포함된 연산의 경우 오버플로우를 막기 위해 계산 단계별로 모듈러 연산을 활용할 수 있다

참고 : 풀이-GitHub링크