BOJ 1009-분산처리

문제

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)

출력

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

예제 입력

5
1 6
3 7
6 2
7 100
9 635

예제 출력

1
7
6
1
9

풀이 방법

  • 데이터가 10개 있다고 하면, 1~10번 컴퓨터를 돌면서 데이터가 하나씩 들어가고, 11번 데이터는 다시 1번 컴퓨터에 들어갈 것이다.
  • 즉 a^b 번째 데이터는 a^b 데이터 결과값의 일의자리 숫자값과 일치하는 컴퓨터에 들어간다.
  • 그러나 a^b 의 결과값을 구하기에는 그 수가 너무 크다.
  • a와 b에 임의의 자연수를 넣고 규칙을 찾아보자.

    2^1 = 2
    2^2 = 4
    2^3 = 8
    2^4 = 16
    2^5 = 32
    2^6 = 64
    2^7 = 128
    2^8 = 256

  • 2^n 의 일의자리 숫자에 2 4 8 6 이 규칙적으로 나오는걸 발견할 수 있다.
  • 2 외에도 2부터 9까지의 숫자들을 a에 대입해서 결과값을 보면, 일의 자리 숫자는 4칸을 간격으로 같은 값이 나오고 있음을 알 수 있다.
  • 일의 자리 숫자만 궁금한 우리의 입장에서는, 2^1 이나 2^5 이나 별 다를게 없다.
  • 따라서 a^b 에서 b는 아무리 큰 숫자가 나오더라도 b = b % 4로 치환해버리면 되나, a^0 = 1 이므로 b === 0 일 때 만 b = 4 로 예외를 둔다. (a^100 === a^4 이므로)
  • 또, a가 두 자리 숫자일 때는 일의 자리만 a에 넣은 것과 결과 값이 같으므로 (2의 제곱과 12의 제곱의 일의자리 숫자는 모두 4), a가 10보다 크면 a = a-10 으로 치환한다.
  • 작아진 a^b 를 문자열로 변환하여 일의자리 숫자만 꺼내온다.
  • 꺼내온 일의 자리 숫자가 0일 때는 10으로 바꿔준다. (0번째 컴퓨터는 존재하지 않으므로)

코드

const fs = require('fs');
const input = fs.readFileSync('input.txt').toString().split('\n');

const count = parseInt(input[0]);
const numbers = [];

for(let i = 1; i < input.length; i++) {
    numbers.push(input[i].split(' '));
}


for(let j = 0; j < count; j++) {
        let a = Number(numbers[j][0]);
        const b = Number(numbers[j][1]);
        if(a >= 10) {
            a = a-10;
        }

        let smallB = b % 4;
        if(smallB === 0) {
            smallB = 4;
        }

        let result = a**smallB;
        result += ''; 
        result = Number(result[result.length-1]);
        if(result === 0) {
            result += 10;
            console.log(result);
        } else {
            console.log(result);
        }
}

좋은 웹페이지 즐겨찾기