[백준OJ] 1323번 숫자 연결하기

www.acmicpc.net/problem/1323

1323번: 숫자 연결하기

---

 

-풀이-

1. 먼저 22를 9로 나눗셈을 봐보자.

이런식으로 나누기를 해주어서 나머지를 구할 수 있다.

 

2. 다음 222를 9로 나누기를 해보자.

위와같이 나머지는 6이 나온다. 여기서 규칙을 찾기 힘들 수 있다. 다음단계를 가보자.

 

3. 2222를 9로 나누기를 해보자.

규칙을 찾았는가?

앞의 1번에서 나온 나머지인 4에 2를 붙인 42를 9로 나눈 나머지 6하고, 222를 9로나눈 나머지 6이 같다는것과,

2번에서 나온 나머지인 6에 2를 붙인 62를 9로 나눈 나머지 8하고, 2222를 9로 나눈 나머지 8이 같다는 것이다.

 

결국, N을 숫자뒤에 붙이고, 나누고, 다시 붙이고,나누고 하면 오버플로우가 나서 절대 안된다.

따라서 N을 K로 나눈 뒤, 0이 나오면 답을 출력하고, 아니면 N을 K로 나눈 나머지 뒤에 숫자를 붙인 뒤, 다시 반복하는 방법을 사용해주면 된다.

 

그럼 0이 계속 안나오면 타임아웃이 나는데, 그 조건은 어떻게 발견할까?

그것은 한번 나온 나머지가 다시한번 또 나온다면, 나머지의 패턴이 계속 반복되는 숫자이므로, 한번 나온 나머지가 다시 나온다면, 과감히 -1을 출력하자.

 

-시간복잡도-

1~K-1 개의 나머지가 정말 우연의 일치로 한번도 겹치지않고 다 나온뒤, 다음번으로 0이아닌 다른 나머지가 나오는 경우가 최악의 경우이므로, O(K)가 된다.

 

-코드-

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

bool check[100001] = { 0 };

long long make_digit(int n) {
	long long digit = 0;
	while (n > 0) {
		digit++;
		n /= 10;
	}
	digit = pow(10, digit);
	return digit;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, k;
	cin >> n >> k;
	long long digit = make_digit(n);
	
	int cnt = 1;
	int remainder = n % k;
	bool flag = true;
	while (remainder != 0) {
		remainder = (remainder*digit + n) % k;
		if (check[remainder]) {
			flag = false;
			break;
		}
		check[remainder] = true;
		cnt++;
	}
	if (flag) {
		cout << cnt << "\n";
	}
	else {
		cout << "-1\n";
	}
	return 0;
}