Project Euler 문제 92번은 숫자의 반복적인 변환 과정을 다룹니다. 기본적으로, 하나의 숫자를 각 자릿수로 나눈 뒤 각각의 자릿수를 제곱하여 더하는 과정을 반복하는데, 모든 숫자는 결국 1이나 89로 수렴하게 됩니다. 이 문제에서 중요한 점은 어떤 숫자들이 89로 도달하게 되는지 찾는 것입니다.
예를 들어 숫자 44로 시작한다고 가정해봅시다. 4의 제곱은 16이므로, 44의 자릿수인 4와 4를 각각 제곱하면 16과 16이 되어 합계는 32입니다. 32를 다시 같은 방식으로 계산해보면 3²과 2²의 합인 13이 됩니다. 이어서 13을 1²과 3²로 계산하여 10을 얻고, 마지막으로 1²과 0²의 합을 통해 1에 도달하게 됩니다. 따라서 44는 최종적으로 1에 수렴하는 수라는 결론에 도달합니다.
다른 예로 85를 살펴보겠습니다. 85의 각 자릿수를 제곱하면 8²과 5²의 합이 되어 89가 나옵니다. 여기서 눈치챌 수 있듯이, 85는 더 이상 다른 수로 가지 않고 89로 “고정”되는데, 바로 이러한 경우가 문제에서 다루고자 하는 핵심입니다. 이와 같은 과정을 통해 85는 1이 아닌 89에 도달하게 됩니다.
이러한 패턴이 모든 수에서 나타나는데, 주어진 수의 범위 내에서 몇 개의 수가 89에 도달하는지 찾아내는 것이 문제의 목표입니다. 예를 들어, 숫자 7로 시작하는 경우를 보더라도 여러 번의 변환 과정을 거쳐 1에 도달한다는 것을 확인할 수 있습니다. 이처럼 특정한 수들은 최종적으로 1에 도달하고, 다른 수들은 89에 도달하는 구조를 가지게 됩니다.
제가 작성한 소스입니다.
//------------------------------------------------
// Project Euler #92 - Square Digit Chains
// - by Aubrey Choi
// - created at 2015-02-08
//------------------------------------------------
#include <stdio.h>
#include <memory.h>
int comb(int n, int r);
void makevector(char v[], int n, int idx);
bool nextvector(char v[], int n);
void printvector(char v[], int n);
int getindex(char v[], int n);
int check(int idx, int n);
int getnum(int idx, int n);
int h[11][11];
char chk89[100000];
int idx89 = 53;
int main()
{
int n = 7;
for( int i = 1 ; i <= 10 ; i++ )
for( int j = 0 ; j <= n ; j++ )
h[i][j] = comb(i+j-1, j);
printf("H(10, %d) = %d\n", n, h[10][n]);
char v[10];
int sum = 0;
chk89[1] = 1;
chk89[idx89] = 2;
for( int i = 1 ; i < h[10][n] ; i++ )
{
if( check(i, n) == 2 ) sum += getnum(i, n);
}
printf("Ans = %d\n", sum);
}
int check(int idx, int n)
{
if( chk89[idx] ) return chk89[idx];
int nidx;
{
char v[10];
makevector(v, n, idx);
int s = 0;
for( int j = 0 ; j < n ; j++ )
s += v[j]*v[j];
for( int j = 0 ; j < n ; j++ )
v[n-j-1] = s%10, s /= 10;
nidx = getindex(v, n);
}
return chk89[idx] = check(nidx, n);
}
int getnum(int idx, int n)
{
char v[10];
makevector(v, n, idx);
int t = n;
int c = 1;
for( int i = 0 ; i < n ; )
{
int count = 1;
for( int j = i+1 ; j < n ; j++, count++ )
if( v[j] != v[i] ) break;
c *= comb(t, count);
t -= count;
i += count;
}
return c;
}
int comb(int n, int r)
{
if( 2*r > n ) r = n-r;
int v = 1;
for( int i = 1 ; i <= r ; i++ )
{
v *= n--;
v /= i;
}
return v;
}
bool nextvector(char v[], int n)
{
n--;
if( v[n] != 9 )
{
v[n]++;
return true;
}
for( int i = n-1 ; i >= 0 ; i-- )
{
if( v[i] < 9 )
{
int c = v[i]+1;
for( ; i <= n ; i++ )
v[i] = c;
return true;
}
}
return false;
}
void makevector(char v[], int n, int idx)
{
int last = 0;
for( int i = 0 ; i < n ; i++ )
{
for( int j = last ; j < 10 ; j++ )
{
if( h[10-j][n-i-1] > idx )
{
last = j;
break;
}
idx -= h[10-j][n-i-1];
}
v[i] = last;
}
}
int getindex(char v[], int n)
{
int idx = 0;
int last = 0;
for( int i = 0 ; i < n ; i++ )
{
int k = 0;
for( int j = 1 ; j < n ; j++ )
if( v[k] > v[j] ) k = j;
for( int j = last ; j < v[k] ; j++ )
idx += h[10-j][n-i-1];
last = v[k]; v[k] = 10;
}
return idx;
}
void printvector(char v[], int n)
{
for( int i = 0 ; i < n ; i++ )
putchar(v[i]+'0');
putchar('\n');
}
숫자의 각 자릿수를 제곱한 뒤 합해 새로운 숫자를 만들어가는 과정을 반복해 89에 도달하는 수의 개수를 계산합니다. 아래는 주요 함수와 그 역할을 설명하는 내용입니다.
주요 변수 설명
int h[11][11];
char chk89[100000];
int idx89 = 53;
• h[11][11]: 조합 계산 결과를 저장하는 2차원 배열로, 각 자리에서 가능한 조합의 개수를 저장합니다.
• chk89[100000]: 숫자들이 1에 도달하는지 또는 89에 도달하는지 체크하는 배열입니다. 1에 도달하면 값이 1로 설정되고, 89에 도달하면 값이 2로 설정됩니다.
• idx89: 값이 89에 도달하는 최초의 인덱스 값입니다.
main 함수
int main()
{
int n = 7;
for( int i = 1 ; i <= 10 ; i++ )
for( int j = 0 ; j <= n ; j++ )
h[i][j] = comb(i+j-1, j);
printf("H(10, %d) = %d\n", n, h[10][n]);
char v[10];
int sum = 0;
chk89[1] = 1;
chk89[idx89] = 2;
for( int i = 1 ; i < h[10][n] ; i++ )
{
if( check(i, n) == 2 ) sum += getnum(i, n);
}
printf("Ans = %d\n", sum);
}
• main 함수는 프로그램의 시작점으로, n 값을 7로 설정합니다.
• 각 자리수에서 가능한 조합을 계산하여 h 배열을 채웁니다.
• chk89 배열의 첫 번째 인덱스와 idx89 인덱스를 각각 1과 2로 초기화해, 각각 1에 도달하는 수와 89에 도달하는 수를 나타냅니다.
• 이후 for 루프를 통해 각 인덱스에서 89에 도달하는 수들을 찾고, 최종적으로 sum 값을 출력합니다.
check 함수
• check 함수는 인덱스 idx와 자리수 n을 인자로 받아서, 해당 숫자가 1에 도달하는지 89에 도달하는지 확인하는 역할을 합니다.
• 인덱스가 이미 확인되었으면 chk89 배열의 값을 반환합니다. 아직 확인되지 않은 경우, makevector 함수를 호출해 v 벡터를 만듭니다.
• v 벡터의 각 자릿수를 제곱하여 s에 더하고, s를 통해 다시 새로운 벡터 v를 만들어 nidx 인덱스를 구합니다.
• chk89[idx]에 check(nidx, n)의 결과를 저장해 메모이제이션을 수행하여 중복 계산을 줄입니다.
getnum 함수
• getnum 함수는 인덱스 idx와 자리수 n을 인자로 받아, 그 인덱스에 해당하는 조합의 개수를 계산합니다.
• makevector 함수로 v 벡터를 만든 뒤, 각 숫자가 몇 번씩 나타나는지 확인합니다.
• 각 숫자 출현 빈도에 따라 comb 함수를 호출하여 조합의 개수를 계산하고, 최종 조합 개수를 반환합니다.
comb 함수
• 조합 계산 함수로, n개 중에서 r개를 선택하는 조합의 개수를 반환합니다.
• 2 * r이 n보다 크면 r 값을 n - r로 대체하여 계산량을 줄입니다.
nextvector 함수
• 벡터 v와 길이 n을 인자로 받아, v의 값을 다음으로 증가시키는 역할을 합니다.
• 끝자리에서부터 시작해 다음 가능한 조합을 만듭니다. 끝자리가 9가 아니면 1을 증가시키고, 끝자리가 9라면 앞자리 수를 증가시킵니다.
• 9까지 도달한 경우 조합을 생성할 수 없으므로 false를 반환합니다.
makevector 함수
• 인덱스 idx와 자리수 n을 이용해 v 벡터를 만듭니다.
• h 배열을 참고해 해당하는 조합의 값을 찾아 벡터 v에 숫자를 할당합니다.
getindex 함수
• v 벡터의 값을 기반으로 인덱스를 계산하여 반환합니다.
• 각 자리의 값을 조합하여 가능한 순서대로 더해주며 인덱스를 계산합니다.
printvector 함수
• 벡터 v를 문자열 형태로 출력해주는 함수입니다.
댓글