[백준] 4375번 1 (C++) - modular 연산

문제

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

4375번: 1

코드

첫 번째 시도(시간초과)

#include <iostream>

using namespace std;

int main(){
  int n;
  while(cin >> n){
    int cnt = 1;
    long long one = 1;
    while(true){
      if(one%n == 0){
        break;
      }
      one=one*10+1;
      cnt++;
    }
    cout << cnt << '\n';
  }

  return 0;
}

 

solution(modular연산 활용)

#include <iostream>

using namespace std;

int main(){
  
  int n;
  while(cin >> n){
    int cnt = 1;
    int one = 1;
    while(true){
      if(one%n == 0){
        break;
      }
      one=one*10+1;
      one%=n;
      cnt++;
    }
    cout << cnt << '\n';
  }

  return 0;
}

정리

첫번째 시도에서 시간초과가 나왔다. one변수에 long long형의 범위를 넘어가는 수가 들어가는 경우가 있었기 때문이었다. 이 문제점을 해결하기 위해서는 다음과 같은 modular 연산의 특징을 이용해야 한다.

x mod N = (x mod N) mod N 

우리는 one을 n으로 나눈 나머지가 0일 때 값을 알아낼 수 있다. 이 조건만 고려하면 되기 때문에 위 modular 연산 특징을 이용해 변수의 일정 범위를 넘지 않기 위해 매번 modular연산(one%=n)을 해주면 이 문제를 풀 수 있다.

참조

https://nanyoungkim.tistory.com/115