분산처리

---

🔗 🔗 전체 1009번 문제

조건

---

문제

---

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

출력

---

각 테스트 케이스에 대해 마지막 데이터가 처리되는 컴퓨터의 번호를 출력한다.

케이스

---

예제 1

---

• 입력

TC
1
2
3
4
5
6
5
1 6
3 7
6 2
7 100
9 635

• 출력

TC
1
2
3
4
5
1
7
6
1
9

풀이

---

문제속에 답이 있다. 1번 컴퓨터부터 10번 컴퓨터까지 데이터를 처리하는데, 가장 마지막에 데이터를 처리하는 컴퓨터의 번호를 반환하면 된다.

데이터 12개가 주어졌다고 가정해보자

위 표를 통해 어렵지않게 규칙을 찾을 수 있다. 데이터를 처리하는 컴퓨터의 번호는 데이터의 1의 자릿수가 가진 값과 동일하다.

즉, 789235번째 테이터는 5번 컴퓨터가 처리한다는 것이다. 789235에서 1의 자릿수가 5이기 때문.

따라서 우리는 주어진 데이터 번호에서 1의 자릿수를 추출하면 된다. 고맙게도 컴퓨터의 갯수가 10으로 고정이다. 데이터의 번호를 10으로 나누면 1의 자리가 나머지로 남으므로, 이를 활용하면 된다.

즉 $a^b \% 10$을 사용하면 된다.

단, 몇가지 주의할 사항이 있다. 첫 번째로, $a^b$의 값이 너무 커지게 되면 연산 퍼포먼스에도 영향을 미치게된다. 그 전에 값이 너무 커지게되면 약간의 오차도 발생한다.

어차피 우리는 1의 자리만 필요하므로 이를 나름 센스있게 우회할 수 있다.

위 표는 7의 3제곱을 차례로 계산한 표다. 어차피 우리는 1의 자리만 필요하므로, 굳이 전체를 계산할 필요 없이, 1의 자리를 기준으로 계산해도 상관없다. 아래의 식을 보면 더욱 명확하다.

$$7^3\text{의 1의 자리} = 49 * 7 \, \% \, 10 = 3$$ $$7^3\text{의 1의 자리} = (49 \, \% \, 10) * 7 \% 10 = 9 * 7 \, \% \, 10 = 3$$

49에서 7을 곱하는게 아니라 일의 자리 9만 구하여 곱함에 주목하자. 두 번째 식과 같이 수의 일의 자리만 계산하는 방법으로 연산의 오버헤드를 줄일 수 있다.

두 번째는 10번 째 컴퓨터에 대한 처리다. 예시로, 30번 째 데이터에 대한 처리 공식은 $30 \, \% \, 10 = 0$과 같다. 계산 결과가 0일 경우 10으로 치환해야 한다.

전체 소스

---

JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 백준 전체 1009 문제 알고리즘 클래스
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/09/a1009">1009 풀이</a>
 * @since 2021.06.09 Tue 11:06:38
 */
public class Main
{
	/**
	 * 메인 함수
	 *
	 * @param args: [String[]] 매개변수
	 *
	 * @throws IOException 데이터 입출력 예외
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			String[] temp = reader.readLine().split(" ");
			
			int a = Integer.parseInt(temp[0]);
			int b = Integer.parseInt(temp[1]);
			
			int result = 1;
			
			for (int j = 1; j <= b; j++)
			{
				result = result * a % 10;
			}
			
			// 0일 경우 10으로 처리
			result = result == 0 ? 10 : result;
			
			System.out.println(result);
		}
		
		reader.close();
	}
}

분류

---

• 수학
• 구현