The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.
Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?
삼각수 수열의 n번째 항은 tn = ½n(n+1)이다. 따라서, 처음부터 열번째까지 삼각수는 다음과 같다:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
단어에 있는 각 글자를 알파벳 순서대로 번호를 매겨 값을 더하여 단어값을 구하게 된다. 예를 들어, SKY의 단어값은 19+11+25=55=t10이다.단어값이 삼각수이면 그런 단어를 삼각 단어라 부른다.
If the word value is a triangle number then we shall call the word a triangle word.
거의 2천개 영어단어가 있는 16K 크기의 문서 파일인 words.txt (우클릭하고 "(으)로 링크 저장")에는, 몇 개의 삼각수가 있는가?
--------------------------------------------------------------------------
파일을 읽어, 단어로 리스트를 구성하고, 각 단어를 읽어서 그 단어가 삼각수이면 카운트를 1씩 추가하는 것이 중심 알고리즘이다. 참고로, 삼각수는 12번 문제에서 한 번 나왔던 개념이다.
이를 구현하기 위해서는 파일을 열어 읽은 내용을 따옴표를 제외하고 문자열을 만드는 것이 첫번째이고, 딕셔너리를 이용해서 각 단어의 단어값을 구하는 것이 두번째이다. 삼각수 여부를 검증하는 것이 필요한데, 가장 긴 단어에 단어길이x26(Z의 값)까지 삼각수를 구한 다음에 각 단어의 단어값이 삼각수 리스트에 있는지 비교하는 방법으로 구현하였다.
삼각수 여부 검증하는 것을 달리 생각해보면 근의 공식을 활용하여 구할 수도 있다. n번째 항을 구하는 공식을 n을 기준으로 근의 공식을 적용하면 n=(-1+(1+8tn)**0.5)/2가 된다. 원래는 +-이지만 이미 -1이 있는데 또 빼면 음수가 되므로 +인 경우만 계산하면 된다. 이렇게 해서 나오는 n이 자연수인 경우 그 단어는 삼각 단어가 되는 것이다.