문제 링크 : www.acmicpc.net/problem/4375
4375번: 1
2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.
www.acmicpc.net
문제
2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.
출력
1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.
접근 방법
숫자를 1, 11, 111, 1111,,,,로 키워가면서 N으로 나눠지는지 따지는 문제이다.
그러나 계속 숫자를 한 자리씩 키워나간다면 long long int 의 범위(-9,223,372,036,854,775,808~9,223,372,036,854,775,807)도 넘어가게 되고 시간초과가 뜬다. 그래서 modular 연산의 활용이 필요하다.
x mod N = (x mod N) mod N 임을 이용해보자.
예를 들어, 111이 N으로 나눠지지 않아서 1111로 넘어갈 때, 1111을 바로 다음 반복문으로 넘기는 것이 아니라 mod N 연산을 해주고 넘기는 것이다. 그러면 숫자가 계속 커지는 것을 방지할 수 있다.
숫자가 매우 커질 때 modular 연산을 이용해서 줄일 수 있다는 것을 기억하자!
//
// 수학_BOJ4375_1.cpp
// Coding_Test_Practice
//
// Created by 김난영 on 2021/04/28.
// Copyright © 2021 KimNanyoung. All rights reserved.
//
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int N;
int k = 0;
while(cin >> N){
int ans = 1;
k = 1;
while(1){
if(ans % N == 0){
break;
}
else{
k++;
ans = ans*10 + 1;
ans %= N; //mod 연산을 해 준 결과를 다음 반복문으로 넘긴다.
}
}
cout << k << "\n";
}
return 0;
}
참고)
while(cin >> input) 은 입력이 종료될 때 까지 받는다.
같은 의미로는 아래와 같다.
while(1){
if(cin.eof() == true) {break;}
}
'Algorithm(BOJ) > Mathematics' 카테고리의 다른 글
| [Java] 백준 1669번 - 멍멍이 쓰다듬기 (1) | 2023.03.12 |
|---|---|
| [C++] 백준 10989번 - 수 정렬하기 3 (메모리 초과 주의) (0) | 2021.06.06 |
| [C++] 백준 1929 - 소수 구하기 (에라토스테네스의 체) (0) | 2021.01.28 |
| [C++]백준 17427번 - 약수의 합 2 (0) | 2021.01.25 |
| [C++]백준 1037번 - 약수 (0) | 2021.01.25 |
