42. 프로젝트 오일러 #42 : 삼각수 단어

이 문제는 알고리즘이 크게 필요하지는 않습니다.

그래서인지 문제의 난이도는 5%입니다.

문제 자체도 상당히 가벼운 편이고요.  검사해야할 단어의 갯수도 많지 않습니다.

이 문제는 영어문자를 A->1, B->2, .. 형식으로 단어를 바꾸면, 숫자의 나열이 되는데, 이 숫자들의 합이 삼각수인 가만 검사하면 됩니다.

삼각수라는 것은 1~n까지의 합 형태가 되면 됩니다.  1, 3, 6, 10, 15, 21, ... 등등이 모두 삼각수입니다.

사실 단어의 수가 길지 않으므로, 간단하게 삼각수 테이블을 만들고 해당 수가 삼각수인지 검사하는 것이 가장 간단하겠죠.  단어의 길이가 40글자라고 해도 글자 하나당 26까지밖에 없으므로 대략 1200까지의 삼각수만 구하면 됩니다.  그러고 나서 해당 값이 채워졌는지만 검사하면 되죠.

제가 구현한 방법은 위 방법은 아니고, 수식을 이용해서 구현했습니다.  단어의 숫자들을 간단하게 i번째 문자(c)라고 했을 때, 아래식을 만족하는 정수 n이 존재하는 가입니다.  정수 n이 존재하기 위해서는 판별식이 제곱수인 가를 알아보면 됩니다.  

판별식만 판단하면 사실 n이 유리수도 될 수는 있습니다만, 판별식이 제곱수라면, 유리수인 n이 발생할 수 없습니다.  판별식은 항상 홀수가 되며, 제곱수라면, 제곱근을 빠져나온 수도 홀수일 수밖에 없습니다.  그래서 반드시 n은 정수가 됩니다.

그래서 나온 소스는 다음과 같습니다.

#include <stdio.h>
#include <math.h>

int main()
{
    const char *words[] =
    {
        #include "p042_words.txt"
    };

    int count = 0;

    for( int i = 0 ; i < sizeof(words)/sizeof(char *); i++ )
    {
        int v = 0;
        for( int j = 0 ; words[i][j] ; j++ ) v += words[i][j] - 'A'+1;
        v = 1+8*v;
        int t = sqrt(v);
        if( t*t == v ) count++;
    }
    printf("Ans = %d\n", count);
}