백준(Baekjoon)알고리즘 <문제번호 1009> - 분산처리

문제

재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다.

1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... ,

10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ...

총 데이터의 개수는 항상 a^b개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라.

 

출력

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

 

풀이

이 문제는 보기에는 단순해 보인다. 그냥 pow함수를 써서 구하면 가능할 것 같았다. 그런데 가만 생각을 해보니 a의 범위와 b의 범위를 보니 100의 1000000승? 감히 컴퓨터도 계산하기 어려울 정도의 어마어마한 숫자이다. 나는 그래서 실험을 해보았다. unsigned_int 범위가 int 보다 양의 정수의 범위가 더 크기 때문에 이 자료형을 써서 풀라는 문제인가? 생각을 해보았지만 그래도 턱도 없는 범위였다.

따라서 나는 일종의 규칙을 찾아보기로 하였다. 내 코드는 눈에 보기에는 아주 단순해 보이지만 나름의 규칙성을 찾아서 알고리즘을 적용한 것 이기 때문에 속도가 나름 빠른 코드이다. 

우선 첫 번째 코드는 내가 pow 함수를 써서 실험한 코드이다.

역시나 오류가 버그가 생기는 것을 볼 수 있다.

그래서 가만히 생각을 해보았다. 1의 6승의 데이터를 10개의 컴퓨터가 나눠서 일을 한다면 10으로 나누고 그 나머지가 일을 하는 숫자 아닐까?라는 생각이 들었고 이에 맞춰서 정리해 보았다.

1>>>>>
1 1 1 1 1 1 1 1 1 1 = 1번째 컴퓨터
2>>>>>
2 4 8 6 2 4 8 6 2 4 = 2 , 4 , 8 , 6 번째 컴퓨터
3>>>>>
3 9 7 1 3 9 7 1 3 9 = 3, 9 ,7 , 1 번째 컴퓨터
4>>>>>
4 6 4 6 4 6 4 6 4 6 = 4, 6 번째 컴퓨터
5>>>>>
5 5 5 5 5 5 5 5 5 5 = 5 번째 컴퓨터
6>>>>>
6 6 6 6 6 6 6 6 6 6 = 6번째 컴퓨터
7>>>>>
7 9 3 1 7 9 3 1 7 9 = 7 , 9 , 3 ,1 번째 컴퓨터
8>>>>>
8 4 2 6 8 4 2 6 8 4 = 8 , 4, 2 ,6 번째 컴퓨터
9>>>>>
9 1 9 1 9 1 9 1 9 1 = 9 , 1 번째 컴퓨터
0 >>>>>
0 0 0 0 0 0 0 0 0 0 = 10번째 컴퓨터

아! 여기서 보면 1, 5, 6은 a를 10으로 나누었을 때의 나머지이다. 왜냐하면 지승을 계산하는 것에서 일에 자리 숫자만 연관이 있기 때문이다. 이는 본인이 직접 생각해보기 바란다. 10의 배수 또한 10번째 컴퓨터만이 마지막 데이터가 처리되는 컴퓨터 일 것이다. 그렇다면 나머지 숫자들은 각각의 n번째 컴퓨터만이 마지막 데이터가 들어갈 수 있는 컴퓨터의 번호들이고 이를 예외 처리하면 끝이 난다. 

※나는 코드를 의식의 흐름대로 작성하였기 때문에 예외처리가 많지만 잘 정리한다면 더 짧은 코드를 작성할 수 있다.

코드

#include <iostream>
using namespace std;
 
int computer = 10;
 
int main()
{
int test_case{};
 
unsigned int a, b, value;
 
cin >> test_case;
 
while (test_case!=0)
{
cin >> a >> b;
if (a < 1 || a >100 || b < 1 || b>1000000)
{
continue;
}
a = a % computer;
 
if (a == 0)
{
cout << 10 << endl;
}
else if (a == 1 || a== 5 || a ==6)
{
cout << a << endl;
}
else if (a == 2)
{
value = b % 4;
if (value == 0)
{
cout << 6 << endl;
}
else if (value == 1)
{
cout << 2 << endl;
}
else if (value == 2)
{
cout << 4 << endl;
}
else if (value == 3)
{
cout << 8 << endl;
}
}
else if (a == 3)
{
value = b % 4;
if (value == 0)
{
cout << 1 << endl;
}
else if (value == 1)
{
cout << 3 << endl;
}
else if (value == 2)
{
cout << 9 << endl;
}
else if (value == 3)
{
cout << 7 << endl;
}
}
else if (a == 4)
{
value = b % 2;
if (value == 0)
{
cout << 6 << endl;
}
else if (value == 1)
{
cout << 4 << endl;
}
}
else if (a == 7)
{
value = b % 4;
if (value == 0)
{
cout << 1 << endl;
}
else if (value == 1)
{
cout << 7 << endl;
}
else if (value == 2)
{
cout << 9 << endl;
}
else if (value == 3)
{
cout << 3 << endl;
}
}
else if (a == 8)
{
value = b % 4;
if (value == 0)
{
cout << 6 << endl;
}
else if (value == 1)
{
cout << 8 << endl;
}
else if (value == 2)
{
cout << 4 << endl;
}
else if (value == 3)
{
cout << 2 << endl;
}
}
else if (a == 9)
{
value = b % 2;
if (value == 0)
{
cout << 1 << endl;
}
else if (value == 1)
{
cout << 9 << endl;
}
}
test_case--;
}
 
}