본문 바로가기

알고리즘 Algorithm/BOJ 백준 (초급~중급)

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

 

링크 : 

 

문제 설명 : 

더보기

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

 

 

입력 : 

더보기

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

출력 : 

더보기

 

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

 

예제 입력 : 

더보기

3
7
9901

예제 출력 : 

더보기

3
6
12

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 1 4375
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define MAX (10000+3)

using namespace std;


int C; // 테스트케이스 개수   
int N; // 인풋 숫자 - 범위

int cache[MAX];

int main() {

	// 1. 입력
	//freopen("input.txt", "r", stdin);
	int input;
	int tmp, ans;
	
	while (scanf("%d", &input) != EOF) {
		tmp = ans = 1;
		while ( 1 ) {
			// ** 탈출조건
			if ((tmp % input) == 0) {
				break;
			}
			tmp = ((tmp * 10) + 1) % input;
			ans++;
		}
		printf("%d\n", ans);
	}

	return 0;
}
#endif
반응형