https://www.acmicpc.net/problem/1009
1009번: 분산처리
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)
www.acmicpc.net
문제
재용이는 최신 컴퓨터 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)
출력
각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.
예제 입력 1
5
1 6
3 7
6 2
7 100
9 635
예제 출력 1
1
7
6
1
9접근 방법
이 문제는 브론즈 II 등급치고는 정답 비율이 약 24%로 꽤 낮은 수치였다.
처음에 어떻게 접근해야할지 막막해서 이것 저것 끄적이다보니 패턴을 발견할 수 있었다.
예를 들어 3 7 을 입력했다고 하자.
이는 총 3^7 개의 데이터가 있고, 이를 순차적으로 1~10까지의 컴퓨터가 처리한다는 의미이다.
따라서 3을 계속 곱하면 3, 9, 27, 81, 243 ... 이 되고, 이를 10으로 나눈 나머지는 3, 9, 7, 1 .. 의 규칙이 생긴다.
따라서 b의 횟수까지 나머지를 계산하면서 결과를 출력하되, 0일 때는 10 을 출력하도록 로직을 짜면 된다.
사실 처음에 이러한 규칙을 수식으로 나타내기 위해 어렵게 생각했지만, 해결 방법은 의외로 간단하다.
for 문의 범위를 b까지 돌리면서 나머지를 구하면 된다.
import java.util.*;
public class Main{
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
for(int i=0;i<n;i++) {
int a=sc.nextInt();
int b=sc.nextInt();
int result=1;
for(int j=0;j<b;j++) {
result=(result*a)%10;
}
if(result==0) System.out.println("10");
else System.out.println(result);
}
}
}