[Baekjoon/백준][1009][C/C++] 분산처리
『목차』
0. 개요
1. 문제
2. 풀이
3. 코드
0. 개요
간단하게 풀릴 줄 알고 호기롭게 풀어나갔지만, 생각보다 시간이 걸렸던 문제이다. 오랜만에 문제 풀이를 해서 그런가 뇌가 굳어있는 느낌. 이 문제의 카테고리는 '수학'과 '구현'이다. '같은 수를 무한히 곱해나갈 시, 일의 자리는 최대 4주기로 같은 수가 반복된다'라는 수학적 원리를 깨달으면 문제는 쉽게 풀린다.
1. 문제
https://www.acmicpc.net/problem/1009
1009번: 분산처리
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다. (1 ≤ a < 100, 1 ≤ b < 1,000,000)
www.acmicpc.net
[문제]
재용이는 최신 컴퓨터 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;
}