4375번 : 1 [C++]

4375번: 1 (acmicpc.net)

4375번: 1

 

1 

다국어

시간 제한        메모리 제한                     제출                         정답                     맞힌 사람             정답 비율

 

1 초

128 MB

15447

5066

3888

32.325%

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

 

예제 입력 1 복사

3
7
9901

예제 출력 1 복사

3
6
12

 

틀린 코드

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

int n;
long long i=1;
string s ="1";
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//1. 입력받기 
	cin >> n;
	//2. 나누어 떨어지는 정수 파악하기 
	while(atol(s.c_str()) % n != 0){
		s += "1";
		i++;
		cout << "i:" << i << "\n";
	}
	//3. 출력하기 
	cout << i;
	
}

overflow가 발생한다.

Logic

선생님 코드

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

int n;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//1. 입력받기 
	while(scanf("%d", &n) !=EOF){
		int cnt = 1, ret=1; //cnt: 만들어갈 나머지, ret: 자릿수 
		while(true){
			//2-1. 나눠지면 출력 
			if(cnt%n==0){
				printf("%d\n", ret);
				break;
			}
			//2-2. 수가 커질때마다 mod 연산 
			else{
				cnt = (cnt*10)+1;
				cnt %= n;
				ret++;
			}
		}
	}

	return 0; 
}

포인트

• 입력의 끝을 정하지 않는 경우, while ( scanf("%d, &n) != EOF ) 또는 while ( cin>>n )을 사용한다.
• mod연산은 미리 mod 연산한 값을 이용할 수 있다.

 

피드백 이후 최종 코드

#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	// 1.입력받기 
	while (cin >> n){
		int v=1, ret=1;
		while (true){
			//나누어 떨어지면 ret 출력 
			if(v%n==0){
				cout << ret << "\n";
				break;
			}
			//숫자를 키워가며 결과를 mod 연산 
			else {
				v = v*10 + 1;
				v %=n;
				ret++; //자리수 +1 
			}
		}
	}
	return 0;
}