티어 : Silver 3 시간 제한 : 1 초 메모리 제한 : 128 MB 알고리즘 분류 : 수학, 브루트포스 알고리즘, 정수론
문제
2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.
출력
1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.
예제 입출력
반응형
우선 알고리즘은 각 자릿수가 1로 이루어진 숫자로 n이 나누어 떨어질 때까지 확인하는 방식을 이용했다.
처음에는 각 자릿수가 1로 이루어진 숫자를 만들기 위해 문자열을 이용했다.
num이라는 string형 변수를 하나 만들어 n으로 나누어떨어지지 않으면 '1'을 추가해주는 방식으로 아래와 같이 구현했다.
#include <iostream>
#include <string>
using namespace std;
int cal_len(long long n){
string num = to_string(n);
return num.length();
}
long long ispossible(int n){
// n의 길이 계산
int len = cal_len(n);
string num;
// n의 길이만큼 1로만 구성된 문자열 만들기
for(int i=0;i<len;i++){
num += '1'; // O(n)으로 동작
}
while(true){
// num이 n의 배수인지 확인
if(num%n==0) return num.length();
// num 한 자리 추가
num += '1';
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
하지만 런타임 에러(out_of_range)로 실패 ㅠ
num += '1';의 연산이 O(n)으로 동작하기 때문에 연산량이 너무 많기 때문이다.
그래서 num 변수를 long long형으로 선언해 동일한 알고리즘을 사용했다.
#include <iostream>
using namespace std;
long long ispossible(int n){
int cnt=1;
long long num=1;
while(true){
// num이 n의 배수인지 확인
if(!(num%n)) return cnt;
// num 한 자리 추가
num = num*10+1;
cnt++;
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
하지만 이 방법도 동일하게 런타임 에러(out_of_range)가 났다.
결과적으로 런타임 에러의 원인은 num이 너무 커지는 것이었는데, num을 줄이기 위해 Moduler(%) 연산을 이용했다.
Algorithm
Brute Force 1. num(long long형)에 1로 이루어진 숫자를 하나씩 담음 2. num이 n으로 나누어 떨어지는지 확인 2-1. 나누어떨어지면 num의 길이 return 2-2. 나누어떨어지지 않으면 num의 길이 증가 (num = num*10 + 1 연산) → 이 때 moduler 연산(num%=n)을 이용해 num의 크기 줄여주는 것이 이 문제의 핵심 !
Code
#include <iostream>
using namespace std;
long long ispossible(int n){
int cnt=1;
long long num=1;
while(true){
// num이 n의 배수인지 확인
if(!(num%n)) return cnt;
// num의 크기 줄여주기
num%=n;
// num 한 자리 추가
num = num*10+1;
cnt++;
}
return -1;
}
int main(void){
int n;
while(true){
cin >> n;
if(cin.eof()) break; // cin.eof(): EOF이면 입력이 취소되고 true 반환
cout << ispossible(n) << "\n";
}
return 0;
}
