The Way

중간에 뜬금없이 끼어있는 어려운 문제. 고민을 꽤 많이 했다. 물론 답을 때려맞추기는 꽤 쉽지만, 답의 정당성까지 보이기는 쉽지 않다. 문제는 다음과 같다. 오각수(pentagon number)는 $P_n = n(3n-1)/2$의 형태로 주어진다. 앞에서부터 1, 5, 12, 22, 35, 51...이 된다. 이제 오각수 한 쌍 $P_i$와 $P_j$를 찾아야 하는데, 두 오각수의 합과 차가 모두 오각수가 되어야 한다. 이를 만족하는 오각수의 쌍 중 두 수의 차이의 최솟값을 구하는 문제이다. 보통은 이렇게 푼다. 적당히 오각수를 생성해놓고(만 개 정도) pair별로 확인하며 합과 차가 둘다 오각수인지 확인한다. 이렇게 코드를 작성하면, 적당히 빠른 시간 안에 5482660이라는 답을 얻을 수 있다. 조금..

요즘은 오일러 도장깨기에 맛들렸다. 간혹가다 흥미로운 문제가 있다. 26번의 경우, 1/n을 소수로 나타냈을 때 반복되는 마디의 수를 구하는 것이 핵심이다. 나눗셈 과정을 역추적하면 이를 구할 수 있는데, 가령 1/14의 마디 수를 구하려면 1 % 14 = 1 10 % 14 = 10 100 % 14 = 2 20 % 14 = 6 60 % 14 = 4 40 % 14 = 12 120 % 14 = 8 80 % 14 = 10 반복되는 마디가 6개이므로, 마디의 길이는 6임을 알 수 있다. 하지만 이 방법을 사용하려면 각 나머지별로 출현했는지 여부를 저장해야 하므로, O(n)의 메모리 공간이 필요하다. 조금 더 좋은 방법이 있을까? 흥미로운 방법이 있는데, n자리가 반복되는 수는 모두 $\frac{x}{99...9..