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

[백준] 분산 처리 문제 ( 브론즈2 )

문제
재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다. - 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... , - 10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ... 총 데이터의 개수는 항상 a^b개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.
입력
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)
출력
각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.
예제 입력	예제 출력
5	테스트 케이스의 개수
1 6	1
3 7	7
6 2	6
7 100	1
9 635	9

 

문제 풀이

해당 문제는 각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 구하는 문제이다.

 

(1) 해당 문제는 먼저 테스트 케이스 만큼의 t의 값을 받기 때문에 반복문을 통해 t만큼 로직을 돌려야 한다.
(2) 데이터 저장 방식

1번 데이터 -> 1번 컴퓨터

2번 데이터 -> 2번 컴퓨터 ...

10번 데이터 -> 10번 컴퓨터

11번 데이터 -> 1번 컴퓨터...

(3) 총 데이터의 개수는 항상 a^b개의 형태로 주어져야 한다.

a = 2 , b = 4 인경우 2^4 이며, 16 거듭제곱값이 나오게 된다.

1~16을 각 컴퓨터에 저장을 하게 되고 조건으로는 11번부터는 다시 1번에 저장을 한다.

결과는 마지막 값인 16이 들어가는 컴퓨터 번호로는 6번이 된다.

(4) 결국 거듭제곱값의 1의 자리 숫자에 따라 들어가는 컴퓨터가 달라진다는 의미이다.

 

그럼 거듭제곱값을 구한 뒤 모듈러 연산자를 통해 1의 자리를 구하면 될까?

- 가능은 하지만, 예제 입력으로는 7 100, 9 635와 같은 엄청 큰 숫자 또한 포함이 되어있다.

- 결국 7의 100승과 9의 635승은 말도 안되는 숫자가 나올 것 이다. ( 연산 범위를 벗어난다는 의미이다. )

 

해결 방법

거듭제곱값에 존재하는 규칙과 모듈러 연산자를 이용하면 된다.

2^1 -> 2 ( 1 = 4 × 0 + 1 ) -> 1

2^2 -> 4 ( 2 = 4 × 0 + 2 ) -> 2

2^3 -> 8 ( 3 = 4 × 0 + 3 ) -> 3

2^4 -> 16 ( 4 = 4 × 1 + 0 ) -> 4

2^5 -> 32

2^6 -> 64

2^7 -> 128

2^8 -> 256

(1) 1의 자리 숫자가 2 , 4 , 8 , 6 으로 반복이 된다. ( 나머지 숫자 또한 반복이 된다. )

결국 문제에서는 거듭제곱값의 1의 자리만을 원하고 있기 때문에 거대한 숫자의 연산 없이도 규칙으로 문제를 해결할 수 있게 된다.

(2) 제곱수와 반복되는 수들의 개수를 모듈러 연산을 한 뒤 나머지를 구하게 되면 거듭제곱값이 몇인지 인덱스로 알 수 있다.

거듭제곱값의 1의자리 -> 2, 4, 8, 6(반복)

거듭제곱값의 나머지 -> 1, 2, 3, 4

(3) 나머지를 구하면 인덱스 반복되는 수의 몇번째 값이 마지막 값인지를 알 수 있게 된다.

 

코드로 구현

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        StringBuilder result = new StringBuilder();

        for (int i = 0; i < t; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int computerNumber = getComputerNumber(a, b);

            result.append(computerNumber).append("\n");
        }

        System.out.print(result);
    }

    private static int getComputerNumber(int a, int b) {
        int lastDigit = a % 10;

        List<Integer> cycle = new ArrayList<>();
        int current = lastDigit;

        while (!cycle.contains(current)) {
            cycle.add(current);
            current = (current * lastDigit) % 10;
        }
        System.out.println(cycle);

        int index = (b % cycle.size() == 0) ? cycle.size() - 1 : (b % cycle.size()) - 1;
        int computerNumber = cycle.get(index);

        if (computerNumber == 0) {
            computerNumber = 10;
        }
        return computerNumber;
    }
}

(1) 반복되는 값을 List에 담아주기

(2) 리스트에서 해당 값이 존재하지 않을 때의 조건을 걸어 반복문을 돌려준다.

(3) 해당 반복문에서는 반복되는 거듭제곱값을 임의로 제곱해주면서 모듈러를 통해 1의 자리만 뽑아서 리스트에 담아준다.

(4) 반복문 조건에 따라 다음 수가 리스트에 담겨있을 경우 반복문을 빠져나가게 된다.

(5) 제곱의 수와 리스트의 크기를 모듈러를 통해 나머지를 구하면 해당 나머지는 거듭제곱값의 마지막 수가 나온다.

(6) 나머지가 0일 경우에는 반드시 리스트 사이즈에 -1을 해 마지막 인덱스의 값을 뽑아준다.

(7) 최종적으로 리스트의 나머지 값이 0일 경우에는 10번 컴퓨터로 만들어준다.