[알고리즘] 분산처리(백준 1009번)

---

keyword : Big
difficulty : 중
completion : ✅
notice :

---

67. 분산처리

📝 문제

재용이는 최신 컴퓨터 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

---

🔍 정답

<오답>

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.math.BigDecimal;  
import java.util.StringTokenizer;  

public class Main {  
    public static void main(String[] args) throws IOException {  

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int input = Integer.parseInt(br.readLine());  
        int result;  

        for (int i=0; i<input; i++) {  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            int a = Integer.parseInt(st.nextToken());  
            int b = Integer.parseInt(st.nextToken());  

            BigDecimal bi = new BigDecimal(Math.pow(a, b));  
            BigDecimal c = new BigDecimal("10");  
            System.out.println(bi);  
            System.out.println(c);  
            result = bi.remainder(c).intValue();  
            System.out.println(result);  
        }  

    }  
}

 

<정답>

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  

public class Main {  
    public static void main(String[] args) throws IOException {  

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        int input = Integer.parseInt(br.readLine());  


        for (int i = 0; i < input; i++) {  
            StringTokenizer st = new StringTokenizer(br.readLine());  
            int a = Integer.parseInt(st.nextToken());  
            int b = Integer.parseInt(st.nextToken());  

            int result = 1;  
            for (int j = 0; j < b; j++) {  
                result = (result * a) % 10;  
            }  
            if (result != 0) {  
                System.out.println(result);  
            } else System.out.println(10);  
        }  
    }  
}

• 기본 풀이는 정수 a의 b제곱으로 나온 수를 10으로 나눈 나머지의 값을 구하면 마지막 데이터가 처리되는 컴퓨터의 번호를 알 수 있다.
  • 5 % 10 = 5 이므로 5번 컴퓨터, 12 % 10 = 2 이므로 2번 컴퓨터, 10 % 10 = 0 으로, 0이 나오면 10을 출력하도록 하면 된다.
• 처음에는 Math.pow를 이용하려고 하였다. Math.pow는 double형이고 7 100처럼 큰 수가 나올 수 있어서 BigDecimal 을 사용하였는데 BigDecimal 범위를 벗어나기도 하였고 계산도 정확하지 않은 것 같았다.
• 23의 3승과 같은 경우 23 * 23 * 23으로 23 / 529 / 12,167 이런 식으로 계산이 되고 23의 일의자리만 계산하면 3 * 3 * 3 해서 3 / 9 / 27 이 나온다.
• 우리가 필요한 것은 일의자리이므로 일의자리만 b만큼 곱해도 같은 결과를 얻을 수가 있다.
• 따라서, b만큼 반복하면서 a의 일의자리를 계속 곱해주고 결과가 0이면 10을 출력하면 된다!