알고리즘
[백준] 분산처리(1009)
84 views
블로그 불러오는 중...
알고리즘

const input =
process.platform === "linux"
? require("fs").readFileSync("/dev/stdin").toString().trim().split("\n")
: require("fs").readFileSync("./input.txt").toString().trim().split("\r\n");
n = parseInt(input[0]);
const getRepeatedLastNumberArr = (a, b) => {
const arr = [a % 10];
for (let i = 0; i < b; i++) {
const lastNumber = (arr[arr.length - 1] * a) % 10;
if (arr[0] === lastNumber) {
return arr;
} else arr.push(lastNumber);
}
return arr;
};
const getLastDataProcessingComputer = (a, b) => {
const lastNumberArray = getRepeatedLastNumberArr(a, b);
const index = b % lastNumberArray.length || lastNumberArray.length;
return lastNumberArray[index - 1] || 10;
};
const result = [];
for (let i = 1; i <= n; i++) {
const [a, b] = input[i].split(" ").map((str) => parseInt(str));
result.push(getLastDataProcessingComputer(a, b));
}
console.log(result.join("\n"));문제의 범위를 확인해 보면 1 ≤ a < 100, 1 ≤ b < 1,000,000이다.
이 경우 직접 a^b를 계산하는 것은 불가능하다.
거듭제곱을 하다 보면, 결국은 패턴(마지막 자리)가 반복된다. 거듭제곱의 마지막 수가 첫번째와 같아지는 순간, 반복은 끝이 난다.
10개의 경우에 직접 시도해 볼 수 있으나, 코드를 이용해서 마지막 자리 수를 반환하는 함수를 만들었다.
그 다음, 해당 함수를 가지고 마지막 자릿수를 기준으로 이제 실제 어떤 컴퓨터에서 처리가 되는지 골라야 한다. b 를 반복되는 만큼 나눠서 마지막 수를 구하는 연산을 줄인다.
마지막 자리 수가 0의 경우, 10번 컴퓨터에서 처리 되는 예외 처리를 해 주어야 하므로 10을 return 하게 하였다.
**0**이면 10번 컴퓨터에서 처리된다.