[C/C++] 프로젝트 오일러 #42 : 삼각수 단어

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

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

 

---

 

어떤 단어의 알파벳 값을 다음과 같이 정의할 수 있습니다. 각 알파벳은 A=1, B=2, C=3, …, Z=26의 값을 가지며, 단어의 알파벳 값은 각 문자에 해당하는 숫자를 더한 값입니다. 예를 들어, “SKY”라는 단어는 S=19, K=11, Y=25이므로, 알파벳 값은 19 + 11 + 25 = 55가 됩니다.

한편, 삼각수(triangle number)는 다음과 같은 공식으로 계산할 수 있습니다.

$$T_n=\frac{n(n+1)}{2}$$

 

여기서 n 은 자연수이며, 예를 들어 첫 몇 개의 삼각수는 1, 3, 6, 10, 15, 21, … 과 같이 됩니다.

주어진 단어 리스트에서 단어의 알파벳 값이 삼각수와 같은 경우, 이를 “Coded Triangle Number”라고 부르고, 문제의 목표는 제공된 단어 리스트에서 “Coded Triangle Number”가 되는 단어의 개수를 찾는 것입니다.

 

---

 

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

 

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

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

 

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

 

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

 

$$\frac{n(n+1)}{2}-\sum c_i$$

 

 

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

 

Triangle Numbers

 

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

//------------------------------------------------
//    Project Euler #42 - Coded Triangle Numbers
//        - by Aubrey Choi
//        - created at 2015-03-29
//------------------------------------------------
#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);
}