[Baekjoon/백준][1009][C/C++] 분산처리

『목차』
0. 개요
1. 문제
2. 풀이
3. 코드

0. 개요

간단하게 풀릴 줄 알고 호기롭게 풀어나갔지만, 생각보다 시간이 걸렸던 문제이다. 오랜만에 문제 풀이를 해서 그런가 뇌가 굳어있는 느낌. 이 문제의 카테고리는 '수학'과 '구현'이다. '같은 수를 무한히 곱해나갈 시, 일의 자리는 최대 4주기로 같은 수가 반복된다'라는 수학적 원리를 깨달으면 문제는 쉽게 풀린다. 

1. 문제

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

1009번: 분산처리

[문제]

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

2. 풀이

[문제 이해]

1번, 11번, 21번, 31번, ... 해서 끝자리(=일의자리)가 1인 데이터들은 1번 컴퓨터가 처리.

2번, 12번, 22번, 32번, ... 해서 끝자리(=일의자리)가 2인 데이터들은 2번 컴퓨터가 처리.

3번, 13번, 23번, 33번, ... 해서 끝자리(=일의자리)가 3인 데이터들은 3번 컴퓨터가 처리.

...

9번, 19번, 29번, 39번, ... 해서 끝자리(=일의자리)가 9인 데이터들은 9번 컴퓨터가 처리.

10번, 20번, 30번, 40번, ... 해서 끝자리(=일의자리)가 0인 데이터들은 10번 컴퓨터가 처리.

 

즉, 데이터의 개수를 알면, 마지막에 처리될 데이터의 번호를 알게 되고, 해당 데이터의 끝자리(=일의자리)를 알게 되면, 몇 번 컴퓨터가 해당 데이터를 처리할지 알게 된다.

 

∴ 입력데이터의 끝자리(=일의자리)를 알아내면 문제는 풀리게 된다.

 

[입력 데이터 형식]

T는 테이스 케이스의 개수. 즉, 입력 데이터의 개수이다.

a는 밑.

b는 지수.

 

∴ $a^b$값의 끝자리(=일의자리)를 알아내면 된다.

 

[직관적인 풀이1] = 오버플로우(Overflow) 발생.

(int)pow(a,b) % 10

단순하게, math.h  라이브러리에 존재하는 pow() 함수를 이용하여 $a^b$값을 구하고, 해당값의 끝자리(=일의자리)를 구하면 어떨까? a의 최댓값은 99, b의 최댓값은 999,999 이므로 pow(99, 999999)의 값은 거의  $100^{10^6}$으로 그 값이 어마무시하게 커진다. 이는 특정 자료형이 감당할 수 있는 크기의 데이터가 아니므로, 컴퓨터는 오버플로우(Overflow) 오류를 발생시키게 된다. 

 

[직관적인 풀이2] = 시간복잡도 O(n). 이 방식으로 풀게되면 시간초과로 오답 처리된다.

#pragma warning(disable:4996) //visual studio scanf 오류 방지.
#include <stdio.h>

int get_units(int a, int b) {
	int units = a % 10;

	for (int i = 1; i < b; i++)
		units = (units * a) % 10;
        
		/*
		units = ( units * (a%10) ) % 10 
		위 식으로 계산해도 된다.
		*/
        
	return units;
}

int main(int argc, char* argv[]) {
	/* 변수선언 */
	int a, b, T;

	/* 입력값 받은 후 연산 */
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d %d", &a, &b);
		printf("%d\n", get_units(a, b) == 0 ? 10 : get_units(a, b));
	}

	return 0;
}

위 코드에서 get_units(int a, int b) 함수는 a와 b를 입력값으로 받아, $a^b$의 끝자리(=일의자리) 수를 반환해 주는 함수이다. 

[직관적인 풀이1]에서 발생한 오버플로우 방지를 위해, %10 연산을 통해 값의 크기를 줄여주고 있다. 다만, 이 방식의 경우 변수 b에 대해 O(n)의 선형적인 시간복잡도를 지닌다. 즉, b의 크기가 커질 경우 시간복잡도도 그에 비례하여 증가한다.

 

역시나 위 풀이대로 백준에 채점을 요청한 결과, 시간초과가 발생한다. 

O(n)에서 시간복잡도를 더욱 줄여야 했는데, 아래 서술할 수학적 원리를 이용하니 O(1) 상수시간 내로 문제가 풀렸다.

 

[정답] = 시간복잡도 O(1)

고민을 해보자. 우리가 구해야 할 값은 $a^b$의 끝자리(=일의자리) 이다. 

$a^b$란 a란 값을 b번 곱했을 때 얻어지는 수이다, b번의 곱셈을 반복했을 때, 일의자리 수의 변화에는 규칙이 존재할까?

	[b%4=1] 1번, 5번, 9번, ..	[b%4=2] 2번, 6번, 10번, ..	[b%4=3] 3번, 7번, 11번, ..	[b%4=0] 4번, 8번, 12번, ..
일의자리 = 0	0	0	0	0
일의자리 = 1	1	1	1	1
일의자리 = 2	2	4	8	6
일의자리 = 3	3	9	7	1
일의자리 = 4	4	6	4	6
일의자리 = 5	5	5	5	5
일의자리 = 6	6	6	6	6
일의자리 = 7	7	9	3	1
일의자리 = 8	8	4	2	6
일의자리 = 9	9	1	9	1

위 표를 통해 '같은 수를 무한히 곱해나갈 시, 일의자리는 최대 4주기로 같은 수가 반복된다' 라는 사실을 깨달을 수 있다.

따라서, 위 표와 같은 배열을 미리 만들어 둔 후, a와 b에 적절한 연산을 통해 값을 서로 매칭시키면 O(1)의 시간 내로 문제가 풀리게 된다.

 

단, 정답 코드에 만들어둔 테이블 = table[10][4] 은 값이 다음과 같은 형태로 저장됨을 유의 바란다.

	[b%4=0] 4번, 8번, 12번, ..	[b%4=1] 1번, 5번, 9번, ..	[b%4=2] 2번, 6번, 10번, ..	[b%4=3] 3번, 7번, 11번, ..
일의자리 = 0	0 [0][0]	0 [0][1]	0 [0][2]	0 [0][3]
일의자리 = 1	1 [1][0]	1 [1][1]	1 [1][2]	1 [1][3]
일의자리 = 2	6 [2][0]	2 ...	4	8
일의자리 = 3	1 [3][0]	3	9	7
일의자리 = 4	6 [4][0]	4	6	4
일의자리 = 5	5 [5][0]	5	5	5
일의자리 = 6	6 [6][0]	6	6	6
일의자리 = 7	1 [7][0]	7	9	3
일의자리 = 8	6 [8][0]	8	4	2
일의자리 = 9	1 [9][0]	9	1	9

 

[주의할 점]

일의 자리 수가 0이라면, 이는 10번째 컴퓨터가 처리하는 값이다. 0번째 컴퓨터가 처리하는 값이 아니다...이것 때문에 몇 번 틀렸다. 조심하자.

3. 코드

#pragma warning(disable:4996) //visual studio scanf 오류 방지.
#include <stdio.h>

int table[10][4]; //테이블 만들기

int power(int a, int b) { //거듭제곱 함수

	if (b == 0)
		return 1;
	else
		return power(a, b - 1) * a;

}

void make_table(void) { //테이블 채워넣기
	
	for (int i = 0; i < 10; i++)
		for (int j = 1; j <= 4; j++)
			table[i][j % 4] = (int)power(i, j) % 10;
		/*
		math.h의 pow()를 이용하여,
		table[i][j % 4] = (int)pow(i, j) % 10; 
		으로 구현해도 된다.
		(math.h 함수는 반환형이 double이므로, int로 형변환 해준다.)
		*/

}

int main(int argc, char* argv[]) {

	/* 변수선언 */
	int a, b, T;

	/* 테이블 만들기 */
	make_table();

	/* 입력값 받은 후 연산 */
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		scanf("%d %d", &a, &b);
		printf("%d\n", table[a % 10][b % 4] == 0 ? 10 : table[a % 10][b % 4]);
	}

	return 0;
}