백준 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)

​

출력

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

​

예제입력

5

1 6

3 7

6 2

7 100

9 635

​

예제출력

1

7

6

1

9

​

크레이의 해설

1번째 작업부터 10번째 작업까지 1 ~ 10번 pc가 맡고, 이후 11번부터 다시 1번부터 시작하여 순차적으로 컴퓨터가 맡는 과정인데요.

2개의 숫자 a, b가 주어지는데 a의 b승에 해당하는 순번에 어느 컴퓨터가 마지막 맡게 되는 것인지 알아 맞추는 프로그램을 짜는 겁니다.

​

만일 3의 7승이라면, 3x3x3x3x3x3x3 = 2,187번째 작업이 되니까, 마지막 작업할 컴퓨터는 7번 컴퓨터가 되는 것이지요.

그냥 단순하게 숫자3을 7번 곱해주면 될 거라 생각하실 수도 있는데요.

​

예제데이터를 보니

7 100, 7의 100승이 있는가 하면,

9 635, 9의 635승도 있습니다.

9을 635번 곱하는 일을 컴퓨터에게 시키면 어떤 일이 일어날까요?

범위초과 오류가 납니다 :)

컴퓨터가 저장할 수 있는 자릿수를 충분히 초과하기 때문이지요.

​

1의 자릿수를 맞추는 문제라서 실수형 변수를 사용하면 분명 오차가 생길테고,

정수형 변수로 계산을 해야 한다고 볼때

C++ 언어가 선언할 수 있는 제일 높은 자릿수 __int64 형 선언도 9,223,372,036,854,775,807 ( 약 920경 ) 이라는 엄청난 숫자를 저장할 수 있지만

단순 곱하기로는 본문에 주어진 최종 결과는 구할 수 없습니다.

​

그렇다면 어떻게 마지막 컴퓨터의 순번을 구할 수 있을까요?

단순한 자연수의 연산 원리 이해가 있으면 쉽게 산출 가능한데요.

​

다음 계산식을 보실까요?

​

344

x129

-------

?

​

이 결과를 암산으로 하려면 꽤 아찔하지만 마지막 자릿수 하나가 뭔지는 금방 알아맞추실 수 있을겁니다. 4 x 9 = 36이므로, 즉 마지막 1자릿수는 6이 됩니다.

다른 숫자의 계산결과는 모두 10 이상의 자리에서 계산이 되지요.

​

그렇다는 것은

9535 에 9를 곱하든 = 85815, 5 에 9를 곱하든 5x9=45 간에 끝자리수 결과는 똑같이 5가 되는 것이지요.

이 문제는 10으로 나눈 나머지를 계속 구하면서 곱하기만 하면 마지막 컴퓨터의 1의 자릿수가 뭔지 알아내는 문제입니다.

​

단 한가지 주의할 점은 마지막 1의 자릿수가 0으로 떨어지는 경우가 있는데,

이 경우 0번 컴퓨터가 답이 아니라 10번 컴퓨터가 답입니다.

이 부분에서 크레이가 좀 헤멘 부분이 있어서 몇번 오답이 났었지요 :)

​

위의 원리를 반영한 1차 소스 살펴볼까요?

 

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

void Result()
{
	// 테스트 케이스를 입력받는다.
	int t;
	scanf("%d", &t);

	// for 문 대신 테스트 케이스값을 1씩 빼면서 테스트하다보면
	// 어느 순간 0이 될때 while 루프를 빠지게 됨
	// for 문보다 간편한 방식
	while(t--){

		// 두 수를 입력받는다.
		long a, b;
		scanf("%ld %ld", &a, &b);

		// 첫번째 값을 넣고
		long result=a;

		// 2번째 제곱부터 b 번째 제곱까지 a 값을 곱한다.
		for(long i=2;i<=b;++i) 
			// 곱하긴 곱하는데 그냥 곱하면 분명 범위 초과가 뜨므로
			// 문제의 목적은 몇번째 컴퓨터를 구하는 것이기 때문에 곱한 다음 
			// 10으로 나눈 몫만을 산출
			result=(result*a)%10;

		// 결과중 0이 나온 경우 0번째 컴퓨터는 없으므로 10번째 컴퓨터라고 명칭한다.
		if(result==0)result=10;

		// 최종 결과 출력
		printf("%ld\n", result);
	}
}

int main()
{
	Result();
	return 0;
}

위 소스를 백준 알고리즘 사이트에서 샘플데이터로 돌려본 결과 약 800ms(밀리초) 정도 나옵니다. 대략 1초지요

 

뭐 이 정도도 괜찮지만 시간을 더 단축할 수 있을까요?

있더라구요 :) 복잡하시면 뭐 넘어가셔도 무방합니다.

​

여기서 한가지 더 살펴볼 원리가 있습니다.

그건 바로 수의 반복입니다.

0~9에 동일한 숫자를 계속 곱할 경우,

일의 자릿수가 0일 경우, 즉 원래 값이10일 경우입니다.이 경우 결과를 계속 곱해봐야 만년 0입니다.

1인 경우에도, 원래의 숫자값이 변하지 않지요. 1 에 1을 100번 곱해봐야 1입니다.

2인 경우 좀 색다른데요. 2x2=4, 4x2=8, 8x2=16, 6x2=12, 이 패턴이 4주기로 반복,

3인 경우 3x3=9, 9x3=27, 7x3=21, 1x3=3, ... 4주기 반복

4인 경우 4x4=16, 6x4=24, 4x4=16, ... 2주기 반복

5인 경우는 5x5=25 이므로 1주기 반복입니다.

6도 5와 마찬가지로 6x6=36 이므로 1주기 반복이구요..

7은 7x7=49, 9x7=63, 3x7=21, 1x7=7, 4주기로 반복,

8은 8x8=64, 4x8=32, 2x8=16, 6x8=48, 4주기 반복

9는 9x9=81. 1x9=9, 2주기 반복

​

즉 모든 숫자가 자신의 숫자에 제곱을 연속해서 곱해줄 경우 1의 자릿수는 최대 4주기마다 똑같은 숫자를 반복하는 것입니다.

그렇다면 100번 제곱하든 4번 제곱하든간에 1의 자릿수의 결과는 똑같다는 것이지요.

제곱회수를 4로 나누었을 때는 0이 되는데 0제곱은 수학에서 결과값이 1이 되므로 예외입니다 :) 이 경우 4로 쳐주면 됩니다

​

그래서 최종소스는 아래와 같습니다.

#include <iostream>
#include <cstring>
#include <string>
using namespace std;

void Result()
{
	// 테스트 케이스를 입력받는다.
	int t;
	scanf("%d", &t);

	// for 문 대신 테스트 케이스값을 1씩 빼면서 테스트하다보면
	// 어느 순간 0이 될때 while 루프를 빠지게 됨
	// for 문보다 간편한 방식
	while(t--){

		// 두 수를 입력받는다.
		long a, b;
		scanf("%ld %ld", &a, &b);

		// 첫번째 값을 넣고
		long result=a;

		// 모든 숫자는 4순환주기마다 100% 동일 숫자가 나온다 ( 연산속도 극적 향상 )
		b = b % 4 + 4;

		// 2번째 제곱부터 b 번째 제곱까지 a 값을 곱한다.
		for(long i=2;i<=b;++i) 
			// 곱하긴 곱하는데 그냥 곱하면 분명 범위 초과가 뜨므로
			// 문제의 목적은 몇번째 컴퓨터를 구하는 것이기 때문에 곱한 다음 
			// 10으로 나눈 몫만을 산출
			result=(result*a)%10;

		// 결과중 0이 나온 경우 0번째 컴퓨터는 없으므로 10번째 컴퓨터라고 명칭한다.
		if(result==0)result=10;

		// 최종 결과 출력
		printf("%ld\n", result);
	}
}

int main()
{
	Result();
	getchar(); getchar();
	return 0;
}

위 소스의 계산 속도는 어떨까요?

아래와 같이 0ms 라는 결과가 나왔습니다 :)