분산처리

문제

백준 1009번 - 분산처리

언어

JavaScript

순서도

일의 자리의 수들에 대해서 반복 배열 정의
정의한 반복 배열을 이용해서 입력된 테스트 케이스에 대해서 몇 번 컴퓨터가 사용되는지 출력

문제 풀이 step 1

10 대의 컴퓨터가 있고, 각 컴퓨터에 1 ~ 10 번까지 번호가 매겨집니다.
1 번 데이터는 1 번 컴퓨터, 2 번 데이터는 2 번 컴퓨터, … 1005 번 데이터는 5 번 컴퓨터 이런 방식으로 각 데이터에 컴퓨터가 할당됩니다.
규칙을 잘 보면 데이터의 번호가 아무리 커도 결국 데이터의 번호의 일의 자리가 컴퓨터의 번호와 대응된다는 것을 확인할 수 있습니다.

문제 풀이 step 2

총 데이터의 개수는 a ^ b 개의 형태로 주어지는데, 문제에서 궁금한 것은 마지막 데이터가 처리될 컴퓨터의 번호입니다.
따라서 a ^ b 를 계산하고, 그 결과값의 일의 자리르 구하면 되겠습니다.
하지만, 굳이 a ^ b 를 계산할 필요는 없습니다. 저희가 필요한 것은 일의 자리의 값이기 때문입니다.
그리고 일의 자리의 특성상 몇 번 곱해져도 특정 개수의 수만큼 반복이 됩니다.
- 예를 들면,
- 1 의 경우, 1 일의 자리를 나열하면 1, 1, 1, 1, 1, … 과 같이 [1] 이 반복됩니다.
- 그리고 3 의 경우, 일의 자리를 나열하면 3, 9, 7, 1, 3, 9, 7, 1, … 과 같이 [3, 9, 7, 1] 이 반복됩니다.
이러한 성질을 이용해서 각 일의 자리 숫자가 곱해질때 어떤 수의 반복이 되는지 배열로 정의합니다.

문제 풀이 setp 3

주어지는 a 에 대해서 10 으로 나머지 연산을 해서 일의 자리값을 먼저 구합니다.
그리고, b 를 일의 자리수의 곱셈 시 반복되는 개수로 나눠서 나머지를 구합니다.
- 예를 들어 일의 자리수가 3 이고, b 가 7 이라면,
- 굳이 3 ^ 7 을 구할 필요없이, 3 은 [3, 9, 7, 1] 이 반복이 되니까
- 7 을 [3, 9, 7, 1]의 개수인 4 로 나눈 나머지를 구합니다.
- 나머지는 3 입니다. 즉, 3 을 3 번 곱했다는 얘기니까 일의 자리는 7 이 됩니다.
- 나머지 값을 바로 [3, 9, 7, 1] 의 인덱스로 사용할 수 없습니다.
- 나머지 값은 3 을 곱한 횟수를 의미하는데 배열에서 0 번 인덱스에 3 이, 1 번 인덱스에 9, 이런식으로 되어있기 때문에
- 나머지 값을 배열의 인덱스로 사용하기 위해서는 -1 을 해줘야 합니다.
위 과정을 통해서 구한 일의 자리의 값을 이용해서, 몇 번 컴퓨터가 사용이 되는지 출력해주면 정답이 됩니다.
추가 설명은 주석에 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	// 각 일의 자리 숫자가 곱해질 때 어떤 수의 반복이 되는지 배열로 정의
	const arr = [];
	arr[0] = [10];
	arr[1] = [1];
	arr[2] = [2, 4, 8, 6];
	arr[3] = [3, 9, 7, 1];
	arr[4] = [4, 6];
	arr[5] = [5];
	arr[6] = [6];
	arr[7] = [7, 9, 3, 1];
	arr[8] = [8, 4, 2, 6];
	arr[9] = [9, 1];

	let t = Number(input[0]);
	let index = 1;
	let res = "";
	while (t-- > 0) {
		const [a, b] = input[index++].split(" ").map(Number);

		// 일의 자리 수 구하기
		const num = a % 10;

		// b 를 일의 자리 수의 곱셈 시 반복 횟수로 나누기
		let numIndex = (b % arr[num].length) - 1;
		if (numIndex < 0) numIndex += arr[num].length;

		// 결과값 출력하기
		res += `${arr[num][numIndex]}\n`;
	}

	return res;
};

console.log(solution(input));