1547902346

이번 포스팅에서는 넥슨 게임프로그래밍직군 테스트에 나왔던 문제인 A-NUMBER라는 문제의 풀이에 대해 포스팅 하고자 한다.

문제가 제법 어렵지만 차근차근 풀다보면 또할만하다.


제곱한 수의 끝에 자기 자신이 나오려면?

우선 가장먼저 해결해야될 문제는1~21억사이의 숫자 x에 대해 F(x)가 참인지 판별하는 방법이다.


​정수를 문자열로 바꾼뒤 비교를 해도 되겠지만 얼핏봐도 꽤나 시간이 많이 소요될법한 전략이다. PASS


​그렇다면 어떤식으로 접근을 해야 할까?
​곱셈이 덧셈을 반복한것이라는 것에 한번 주목하여 F(x)가 참인 수들을 한번 살펴보자

​5 -> 10 -> 15 -> 20 -> 25
​625 -> 1250 -> 1875 -> ............... -> 390000 -> 390625
​뭔가 눈에 보이는게 있는가?


​그렇다 마지막으로 더하기 직전에 뒷자리가 0으로 채워져야 함을 볼수 있다.
​다시말해 (x)*(x-1)은 10^xLength의 배수여야 x^2에서 뒷자리에 x가 나타날수 있다.

  • xLength는 x라는 숫자의 길이를 의미 x가 1이면 xLength는 1, x가 123이면 xLength는 3, x가 111이면 Length 는 3

이런 판별법을 코드로 옮기면 다음과 같다.


int GetLength(long long  num);			// 숫자의 길이를 구하는 함수

long long tenPowers[MAX_POWER];			// 10의 제곱수들을 저장할 배열

// F(num)
bool FJudge(long long num)
{
	long long mul = (num) * (num - 1);
	int numLength = GetLength(num);

	if (mul % tenPowers[numLength] == 0)
	{
		return true;
	}
	return false;
}


판별은 빨라졌지만 판별해야할 수가 너무 많다!

이제 판별자체는 굉장히 쉬워졌다. 그럼에도 아직 이 문제를 풀기에는 역부족이다.

아무리 판별이 빨라졌다 한들 판별해야할 수가 21억개고 이는 너무 큰 숫자이고 이렇게 많은 숫자를 판별하는데는 너무나도 많은 시간이 소요된다.

따라서 판별해야될 수 자체를 줄여주는 작업이 필요하다. 어떻게 하면 줄일수 있을까?

​​

10^xLength의 배수는 바꿔말해 해당 숫자를 소인수 분해했을때 2와 5가 최소 xLength개씩 있어야 한다는 것을 의미한다. 즉 (x)*(x-1)을 소인수 분해 했을때 2와 5가 최소 xLength개씩 있어야 된다는 말이다.

그런데 잘 살펴보면 x와 x-1둘중 한쪽에  (2*5*5) 이렇게 2와 5가 중복으로 들어간 수는 절대 있을수 없음을 알수 있다.

n의 배수에다가는 1을 n번 더해야만 다시 n의 배수가 될수 있기 때문에 x와 x-1이 둘다 같은수의 배수일수는 없다.​

결국 x와 x-1이 각각 2^xLength혹은 5^xLength의 배수여야 함을 알수 있다.

*한쪽이 10^xLength인 경우도 되지 않을까 생각할수 있는데 10^n은 길이가 n+1이다. 그래서 한자리가 부족하기 때문에 될수가 없다.

결국 ((a*2^xLength) * (b*5^xLength)) % 10^xLength = 0인 값을 찾고자 하는것이고 어차피 한쪽이 정해지면 남은 한쪽 역시 정해지는 것이니(x*(x-1)의 관계기때문) 개수가 더 적을것 같은 (b*5^xLength)들을 후보로 설정해 보자.

5^xLength의 배수중 10^xLength보다 작은수들을 찾아내 후보로 등록하면된다.

이를 코드로 옮기면 아래와 같다.

const int MAX_POWER = 10;				// 지수의 최대 크기

long long fivePowers[MAX_POWER];		// 5의 제곱수들을 저장할 배열
long long tenPowers[MAX_POWER];			// 10의 제곱수들을 저장할 배열

set<long long > candidateNum;			// 후보들

// 후보들을 구함 (5^xLength의 배수중 10^xLength보다 작은 값들)
for (int i = 0; i < MAX_POWER; i++)
{
	candidateNum.insert(fivePowers[i]);
	long long scale = 2;

	while (scale * fivePowers[i] < tenPowers[i])
	{
		candidateNum.insert(scale * fivePowers[i]);
		scale++;
	}
}

이제 구해진 후보들을 판별하기만 하면 끝!

이제는 이 set에 들어간 수를 x혹은 x-1이라고 가정하고 판별을 해보면된다

num이 x라고 가정하면 F(num)이 참인지를 검사해서 참이면 num을 set에 넣어주고 num이 x-1이라고 가정할경우는 F(num+1)이 참인지를 검사해서 참이면 (num+1)을 set에 넣어주면된다.

bool FJudge(long long num);				// F(num)

set<long long > candidateNum;			// 후보들
set<long long > ans;					// F(x)가 참인 수들

// 이제 각 후보들에 대한 검사를 실시
for (auto num : candidateNum)
{
	// num이 x라고 가정할때
	if (FJudge(num))
	{
		ans.insert(num);
	}

	// num이 x-1이라고 가정할때
	if (FJudge(num + 1))
	{
		ans.insert(num + 1);
	}
}

전처리된 데이터를 이용하여 쿼리에 대한 답 출력

이제는 전처리를 쭉하고 들어오는값 받아서 뭐 이분탐색을 하던 선형탐색을 하던 하면된다.

set<long long > ans;					// F(x)가 참인 수들
int ansNum = -1;

// 돌면서 크거나 같은 수를 발견하면 브레이크
for (auto num : ans)
{
	if (num >= n)
		break;
	ansNum = num;
}

// 출력
cout << ansNum << endl;

전체 코드

#include <iostream>
#include <set>

using namespace std;



int GetLength(long long  num);			// 숫자의 길이를 구하는 함수
bool FJudge(long long num);				// F(num)


const int MAX_POWER = 10;				// 지수의 최대 크기


long long fivePowers[MAX_POWER];		// 5의 제곱수들을 저장할 배열
long long tenPowers[MAX_POWER];			// 10의 제곱수들을 저장할 배열


set<long long > candidateNum;			// 후보들
set<long long > ans;					// F(x)가 참인 수들



int main()
{
	long long five = 1;
	long long  ten = 1;

	// 제곱수들을 미리 구함
	for (int i = 0; i < MAX_POWER; i++)
	{
		fivePowers[i] = five;
		five *= 5;

		tenPowers[i] = ten;
		ten *= 10;
	}


	// 후보들을 구함 (5^xLength의 배수중 10^xLength보다 작은 값들)
	for (int i = 0; i < MAX_POWER; i++)
	{
		candidateNum.insert(fivePowers[i]);
		long long scale = 2;

		while (scale * fivePowers[i] < tenPowers[i])
		{
			candidateNum.insert(scale * fivePowers[i]);
			scale++;
		}
	}

	// 이제 각 후보들에 대한 검사를 실시
	for (auto num : candidateNum)
	{
		// num이 x라고 가정할때
		if (FJudge(num))
		{
			ans.insert(num);
		}

		// num이 x-1이라고 가정할때
		if (FJudge(num + 1))
		{
			ans.insert(num + 1);
		}
	}


	// 이제 수를 입력 받아서
	int n;
	cin >> n;

	int ansNum = -1;

	// 돌면서 크거나 같은 수를 발견하면 브레이크
	for (auto num : ans)
	{
		if (num >= n)
			break;
		ansNum = num;
	}

	// 출력
	cout << ansNum << endl;
	return 0;
}



// 숫자의 길이를 구하는 함수
int GetLength(long long  num)
{
	int numLength = 0;
	while (num > 0)
	{
		numLength++;
		num /= 10;
	}
	return numLength;
}



// F(num)
bool FJudge(long long num)
{
	long long mul = (num) * (num - 1);
	int numLength = GetLength(num);

	if (mul % tenPowers[numLength] == 0)
	{
		return true;
	}
	return false;
}

문제 출처

(C++/STL) A-NUMBER (넥슨 기출문제)
함수를 만들고 함수의 파라미터에 넣은 값을 곱하여 그 결과값이 자릿수 만큼 맨 뒷자리가 같으면 true, 틀...