7854. 최약수

[1. 정의]

• 최약수: 앞에 어떤 숫자를 붙여도 자기 자신을 약수 갖는 수.
  • 예제
    • 2 앞에 어떤 수를 붙여도 해당 수는 2를 약수로 갖는다.
      • 12
    • 5 앞에 어떤 수를 붙여도 해당 수는 5를 약수로 갖는다.
      • 38275

[2. 요구 사항]

• 임의의 숫자 X 가 있을 때, X 보다 작거나 같은 최약수의 개수
  • X 의 범위는 [1, 10^9]

[3. 해결 방법]

주어진 조건을 만족하는 수를 다음과 표현 할 수 있다.

T = (R+X)

T % X == 0

• X = a*10^N + b*10^(N-1) + ... + z*10^0
  • 각 계수는 모두 0 이 아닌 자연수
  • N < 9 인 경우 0 < [a ~ z]  < 10
  • N == 9 인 경우, a == 1 이고 [b ~ z] 는 모두 0
• R = a`*10^(N+1) + b`*10^(N+2) + ...
  • 각 계수는 모두 0 이 아닌 자연수
  • 0 < [a` ~ ] < 10

N == 0 인 경우,

• 1 <= (X = z) < 10
• R = 10a` + 100b` + ...
• T = (10a` + 100b` + ... ) + z
• X 가 1, 2, 5 인 경우 R 과 공약수를 갖게 되어 나누어 떨어지게 된다.

N == 1 인 경우,

• 10 <= (X = (10y + z)) < 100
• R = 100a` + 1000b` + ...
• X 가 10, 20, 25, 50 인 경우 R 과 공약수를 갖게 됨.

N == 2 인 경우

• 100 <= (X = (100x + 10y + z)) < 1000
• R = 1000a` + 10000b` + ...
• X 가 100, 125, 200, 250, 500 인 경우 R 과 공약수를 갖게 됨.

결과적으로 N 을 X 의 digit 개수라 할 때,

10^(N+1) 의 공약수 중 X 보다 작거나 같은 값들이 최약수가 된다고 볼 수 있다.

 

[4. 코드]

static vector<int> table[10];

static void table_init()
{
	table[0].push_back(1);
	table[0].push_back(2);
	table[0].push_back(5);

	table[1].push_back(10);
	table[1].push_back(20);
	table[1].push_back(25);
	table[1].push_back(50);

	table[2].push_back(100);
	table[2].push_back(125);
	table[2].push_back(200);
	table[2].push_back(250);
	table[2].push_back(500);

	for (int i = 3; i < 9; i++)
	{
		int j = i - 1;
		for (int idx = 0; idx < table[j].size(); idx++)
		{
			table[i].push_back(table[j][idx] * 10);
		}
	}

	table[9].push_back(1000000000);
}

static int digit_len(int n)
{
	int div = 10, ret = 1;

	while (n / div)
	{
		div *= 10;
		ret += 1;
	}

	return ret;
}

static int solution(void)
{
	int N, len, ret = 0, i;
	cin >> N;

	len = digit_len(N);
	
	for (i = 0; i < len - 1; i++)
		ret += table[i].size();

	for (int idx = 0; idx < table[i].size() && N >= table[i][idx]; idx++)
		ret += 1;

	return ret;
}

table_init() 은 main()에서 먼저 선행되어야 한다.

하드코딩한 감이 없지 않아 있지만, 일단은 pass가 되어서 괜찮은 것 같다.

내가 이 문제를 해결한 방법은 아래와 같다.

 

먼저 len(N)을 N의 길이라 하겠다. len(100) = 3, len(2) = 1 이런 느낌이다.

그래서 문제에서 요구하는 값을 구하려면 아래와 같아야 한다.

(aaaaaa10^(len(N)) + N) / N 이 나누어 떨어져야하고, 이렇게 되기 위해

N은 10, 100, 1000 ... 등의 약수여야 한다.

다만, 몇가지 제한이 있는데, 

N이 100 = {1, 2, 4, 5, 10, 20, 25, 50, 100} 이라면

될 수 있는 값은 1 < len(N) < 3 인 것만 된다는 것이다.

그래서 이 중 10, 20, 25, 50 만 문제에서 요구하는 값이 될 수 있는 것이다.

 

그래서 이러한 규칙을 찾으면 아래와 같다.

 

1, 2, 5 - a

10, 20, 25, 50 - b

100, 125, 200, 250, 500 - c

1000, 1250, 2000, 2500, 5000 - d

...

 

a 에서 b로 b에서 c로 넘어갈때 각 값의 10 씩 곱해서 넘어가면 되는데,

이를 2로 나누어서 중복된 값이 없으면 추가하고 있으면 그냥 넘어가는 식이다.

이 부분을 table_init() 에서 하드코딩해서 넘어 갔다.

d 이 후는 2로 나누면 이미 중복된 값이 있기 때문에 굳이 이 부분을 신경쓰기 않아도 된다.

또 한 그 값들이 오름차순으로 정렬된다.