[백준알고리즘] 1009번: 분산처리 -C++

[백준알고리즘] 1009번: 분산처리 -C++

1009번: 분산처리 (acmicpc.net)

1009번: 분산처리

모듈로 연산을 해주었다. 모듈로(\(\%\))란 나머지라고 생각하면 된다.

모듈로 연산을 사용해준 이유는, 컴퓨터가 \(10\) 대면서 하나씩 일을 순차적으로 맡아가기 때문에 적합하다고 생각했다.

 

예를 들어서, \(11\)개의 데이터가 주어진다면 마지막 데이터를 처리하는 컴퓨터는 \(11\%10 = 1\) 번 컴퓨터가 될 것이다. 또한 \(26\) 개의 데이터가 주어진다면 마지막 데이터를 처리하는 컴퓨터는 \(26\%10 = 6\) 번 컴퓨터가 될 것이다.

마찬가지로, \(2^5\)개의 데이터가 주어진다면 마지막 데이터를 처리하는 컴퓨터는 \(2^5\%10 = 2\) 번 컴퓨터가 될 것이다.

그렇기 때문에 모듈로 연산으로 마지막 컴퓨터를 알 수 있는 것이다.

 

---

 

모듈로 연산 중에는 다음과 같은 특징이 존재한다.

$$(A*B)\%m = ((A\%m) * (B\%m))\%m$$

 

이러한 특징을 이용해 다른 분들은 일일이 a를 곱해가면서 오버플로우가 발생하지 않게 모듈로 연산을 해주었다.

$$A^{n+1}\%m = ((A^n\%m) * (A^1\%m))\%m$$

 

하지만, 이러한 방법들은 일반적으로 큰 제곱승을 갖는 수에 대해서 비효율적이다. \(a^b\)에 대해서 \(a\)를 일일이 \(b\)번 곱하는 것보다 빠른 모듈로 거듭제곱법이라는 것이 있다. 다른 포스팅에도 몇 번 언급했지만, 다음과 같은 위의 모듈로 연산의 특징을 이용하면 다음과 같이 구할 수도 있다.

$$A^{2n}\%m = ((A^n\%m)*(A^n\%m))\%m$$

 

이해를 쉽게 하기 위해서 \(2n\) 승을 예로 들었지만, \(12\) 거듭제곱이라면 \(6\) 거듭제곱을 두 번 할 수도 있지만, \(8\)거듭제곱과 \(4\)거듭제곱을 이용하는 것도 가능하다. 더 쉬울 수도 있다. 왜냐하면, \(4\) 거듭제곱의 모듈로를 통해 \(8\) 거듭제곱의 모듈로를 쉽게 만들 수 있기 때문이다.

 

---

 

아무튼, 위의 언급한 모듈로 연산, 그리고 빠른 모듈로 거듭제곱법을 이용해 마지막 데이터 처리 컴퓨터의 번호를 구했다.

 

다만, \(0\) 의 거듭제곱은 \(0\) 이고, \(1\)의 거듭제곱은 \(1\)이기 때문에 이 두 경우는 재귀를 하지 않고 즉시 return하도록 했다. 또한, \(x\)의 \(1\) 거듭제곱은 \(x\)이기 때문에 이 경우에도 즉시 return 했다.

 

마지막으로, \(0\)번 컴퓨터는 없으며 \(0\)번 컴퓨터가 \(10\)번 컴퓨터의 역할이기 때문에 이 경우에만 출력에 신경을 써주었다.

 

아래는 위의 방법으로 풀이한 C++ 코드다.

#include <iostream>
#include <algorithm>
#include <vector>

void solve(void);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);

	solve();
}

int find_modulo(int a, int b)
{
	if (1 == a || 0 == a) return a;
	if (1 == b) return a % 10;
	int half = b / 2;
	int remain = b - half;

	return (find_modulo(a, half) * find_modulo(a, remain)) % 10;
}

void solve(void)
{
	int test_case;
	std::cin >> test_case;

	for (int t = 0; t < test_case; t++)
	{
		int a, b;
		std::cin >> a >> b;

		int answer = find_modulo(a, b);
		std::cout << (answer ? answer : 10) << '\n';
	}
}

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다