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);
}
}
Author And Source
이 문제에 관하여(BOJ 1009-분산처리), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@goody/BOJ-1009-분산처리저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)