문제 설명

백준 분산처리 문제 풀이(https://www.acmicpc.net/problem/1009)

코드 구현

javascript

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번 컴퓨터에서 처리된다.