[백준] 1009번 : 분산처리 – JAVA [자바]

https://www.acmicpc.net/problem/1009

1009번: 분산처리

 

---

• 문제

 

 

---

• 문제 풀이

백준 1009번 분산처리는 브론즈 3 난이도의 구현 및 수학 문제이다. 이 문제는 난이도의 비해 정답 비율이 조금 낮은 거 같다. 우선 이 문제에서는 10대의 컴퓨터가 있다. 그리고 이 10대의 컴퓨터가 데이터를 처리하는데 1번 데이터는 1번 컴퓨터에서, 2번 데이터는 2번 컴퓨터에서 데이터가 처리된다. 나머지들도 마찬가지이고 11번 데이터는 다시 1번 컴퓨터에서 처리된다.

 

이때 a^b가 주어졌을 때 마지막 데이터가 처리되는 컴퓨터의 번호를 출력하면 된다. 먼저 드는 생각은 그냥 a^b를 하고 나머지를 이용해서 구하는 것이다. 하지만 그러면 int형과 long형의 범위를 초과한다. 그렇다고 해서 BigInteger를 쓰면 메모리 초과가 나온다.

 

즉, 다른 방식으로 이 문제를 접근해야 한다. (a^b) % n = (a % n) × (a % n)... 를 b번 한 것과 같다. 따라서 이 문제는 for-loop을 쓰면 쉽게 풀 수 있다.

 

여기서 나머지 10을 구하는데 만약에 나머지가 0이면 어차피 계속 나머지가 0이므로 10번 컴퓨터에서 데이터가 처리된다는 것을 알 수 있다.

 

---

• 코드

 

import java.io.*;
import java.math.BigInteger;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            if (a % 10 == 0) {
                sb.append(10 + "\n");
                continue;
            }
            int num = a % 10;
            for (int j = 1; j < b; j++) {
                num = (num * a) % 10;
            }
            sb.append(num + "\n");
        }
        System.out.print(sb);
    }
}

 

---

• 후기

브론즈 3 문제치고는 정답 비율이 되게 낮은 문제였다.