31번 문제, 76번 문제를 조금 변형시켜 만들어진 문제이지만, 슬프게도 31번 문제, 76번 문제를 해결하는데 사용한 방법을 적용할 수 없었다. 31번 문제는 동전 숫자를 알아서 반복문을 중첩시켜 해결했고, 76번 문제는 정수론에 있는 분할수 공식을 이용해서 구했는데 이 두가지와는 성격이 달라 그대로 적용할 수 없었다.
영문 위키 Partition(Number Theory) 항목의 Restrcted partition을 잘 이해하면 적용 가능할 것 같은데 이제는 중학교 수준 이하의 실력을 가진 상황에 그 부분을 이해하고 프로그래밍 하는 것이 쉽지 않았다.
그래서, 31번, 76번 문제 모두에 적용가능했던 동적 프로그래밍 방법을 가져와 소수에 맞게 조금 응용해서 해결했다. 정답을 맞췄지만 내 것으로 소화한 것이 아니어서 찝찝함이 남는다.
예시를 제외하면 문제는 2줄 밖에 안되지만, 막상 구현하려 하면 간단한 것이 아니었다. 문제31의 변형이어서 그 때 사용한 방법을 적용하려 보니 31번에서는 8종류의 동전을 이용하는 8중 반복문을 이용해서 구현했는데, 이 문제는 그 경우 99종류의 동전이 있기 때문에 99중 반복문을 구현해야 가능한 것이었다. 그렇게 해결할 수도 있겠지만 문제에서 원하는 방법이 그것이 아니어서 고민을 많이 했는데 해결책이 떠오르지 않아 많이 애를 먹었다.
가장 간단하게 해결하는 것은 동적 프로그래밍을 이용하는 것인데, 다른 사람이 해결한 코드를 보면 간단하지만 왜 그렇게 답이 나오는지 이해가 되지 않아 많이 난감했다.
그래서 관련 내용을 추가로 찾아보니 이 문제는 정수론(number theory)이나 이산수학(Discrete Mathematics)에서 다루는 분할수(Partition Number) 문제라고 한다. 답을 구하는 방법으로 오일러의 오각수 정리, 하디-라마누잔-라데마커 공식과 같은 것이 있는데 오일러의 오각수 정리를 이용해서 답을 구했다. 위키피디아 보다는 나무위키의 분할수 항목에 프로그램으로 구현 가능하도록 공식이 나와 있어 그것을 이용했다.
Each of the six faces on a cube has a different digit (0 to 9) written on it; the same is done to a second cube. By placing the two cubes side-by-side in different positions we can form a variety of 2-digit numbers.
For example, the square number 64 could be formed:
In fact, by carefully choosing the digits on both cubes it is possible to display all of the square numbers below one-hundred: 01, 04, 09, 16, 25, 36, 49, 64, and 81.
For example, one way this can be achieved is by placing {0, 5, 6, 7, 8, 9} on one cube and {1, 2, 3, 4, 8, 9} on the other cube.
However, for this problem we shall allow the 6 or 9 to be turned upside-down so that an arrangement like {0, 5, 6, 7, 8, 9} and {1, 2, 3, 4, 6, 7} allows for all nine square numbers to be displayed; otherwise it would be impossible to obtain 09.
In determining a distinct arrangement we are interested in the digits on each cube, not the order.
{1, 2, 3, 4, 5, 6} is equivalent to {3, 6, 4, 1, 2, 5} {1, 2, 3, 4, 5, 6} is distinct from {1, 2, 3, 4, 5, 9}
But because we are allowing 6 and 9 to be reversed, the two distinct sets in the last example both represent the extended set {1, 2, 3, 4, 5, 6, 9} for the purpose of forming 2-digit numbers.
How many distinct arrangements of the two cubes allow for all of the square numbers to be displayed?
두 개의 육면체의 각 면에 0~9 사이의 글자가 있는 경우, 두 육면체를 나란히 두면 다양한 2자리 숫자를 만들 수 있다.
예를 들어, 제곱수인 64는 아래와 같이 만들어진다:
실제로, 두 육면체의 숫자를 잘 정하면 100 이하의 모든 제곱수를(01, 04, 09, 16, 25, 36, 49, 64, 81) 표시할 수 있다.
예를 들어, 한 육면체에 {0, 5, 6, 7, 8, 9}, 다른 육면체에 {1, 2, 3, 4, 8, 9}가 있으면 모든 제곱수를 표시하는 한 방법이 된다.
그러나, {0, 5, 6, 7, 8, 9}와 {1, 2, 3, 4, 6, 7}가 9개 제곱수를 모두 표현하기 위해서는 6, 9는 아래위가 뒤집힌 경우를 허용해야 한다. 그렇지 않으면 09를 만들 수 없다. 유일한 배열을 결정하기 위해 각 육면체의 배열은 중요하지만 순서는 아니다.
{1, 2, 3, 4, 5, 6}과 {3, 6, 4, 1, 2, 5}은 동일하다. {1, 2, 3, 4, 5, 6}과 {1, 2, 3, 4, 5, 9}은 서로 다르다.
그러나, 6과 9가 뒤집어지는 것을 허용했으므로, 마지막 예시 두 가지 모두 2자리 수를 만들기 위한 확장된 집합인 {1, 2, 3, 4, 5, 6, 9}를 나타내고 있다.
문제 지문이 긴데, 두 수를 조합해서 제곱수(01, 04, 09, 16, 25, 36, 49, 64, 81)을 만들어낼 수 있는 주사위 번호 조합이 몇가지 만들 수 있는지에 대한 질문이다. 처음에 하나는 10의 자리, 다른 하나는 1의 자리를 두는 조합을 생각했는데, 문제에서 요구하는 것은 주사위가 특정 자리에 고정되지 않고 제곱수를 만들어 낼 수 있는 조합을 요구하기 때문에 조금 더 고민을 해야 되었다.
순서가 다르더라도 동일하다고 했으므로 10개의 숫자(0~9)에서 6개 숫자를 뽑는 조합으로 리스트를 만들고, 두 조합 리스트(주사위 2개)에서 제곱수가 만들어지는 경우를 확인할 수 있도록 했다. 10C6에 해당하는 조합 크기가 210이어서 생각보다 크지 않고, 이 문제를 해결하기 위한 새로운 알고리즘이 있을 것 같지는 않아서 반복문 2개를 이용하는 전수조사(라고 좋게 표현했지만 brute force) 방식으로 해결하기로 했다.
6, 9를 동일한 경우로 판정하는 것은 어렵지 않았는데 오답으로 판정되어 문제의 원인을 찾느라 여러가지 방법을 적용해보느라 해결하는데 시간이 많이 걸다. 실제 문제가 된 것은 두 주사위를 독립사건으로 보고 210x210의 전수 대상으로 조사했지만 이 경우 문제에서 예시로 제시한 {0,5,6,7,8,9}, {1,2,3,4,8,9}와 {1,2,3,4,8,9}, {0,5,6,7,8,9}를 두 번 계산하기 때문에 결과값이 크게 나오고 있었고, 이 부분이 중복되지 않도록 조정하고 나서 정답을 구할 수 있었다.
문제 요구조건을 잘못 이해해서 시간이 많이 걸렸어도 복잡한 알고리즘을 요구하는 문제는 아니었는데, 나중에 확인해보니 처음으로 해결한 40% 난이도의 문제였다.
71번 문제에서 몇글자 다른데 전혀 다른 문제가 되어 있다. 71번과 마찬가지로 분자가 분모보다 작고, 분자와 분모의 최대공약수가 1이 되는 분수 집합을 전제로 하고, 이번 문제에서는 그런 약분된 진분수가 분모가 1,000,000 이하인 경우 몇 개 있는지 물어보고 있다.
71번 문제에서는 전체 분수 값이 정렬된 상태를 요구했지만, 이번 문제는 정렬하는 과정 없이 답을 구할 수 있으므로 조금 더 쉽게 접근이 가능할 것 같다. 특정 분모 숫자에 대한 공약수가 1인 분자의 갯수는 69번 문제, 70번 문제를 해결할 때 사용했던 Φ(n)을 구하는 것과 동일하다. 다만, 69, 70번은 특정 조건을 만족하는 소수를 대상으로 계산하면 되었지만, 이번 문제는 가능한 분모 전체를 대상으로 구해야 하기 때문에 시간을 더 많이 요구하고 있다.
기존 문제에 사용한 방법을 이용해서 계산해봤지만, 1만개 계산에 6분 이상 소요되면서 전체를 계산하려면 최소 10시간 이상이 필요할 것으로 전망되어 다시 난감함을 느끼게 되었다. 특정 숫자에 대한 파이값을 계산하는 공식을 구글링을 통해 찾아 적용했는데(예를 들어 3과 5가 약수인 Φ(75)=75*(1-1/3)*(1-1/5)), 그래도 생각보다 시간이 많이 소요되었다. 몇가지 최적화를 해서 2시간 이상 실행 끝에 오답을 구했다.
각 숫자를 소인수분해 해서 공식을 적용했는데 프로그램을 잘 못 구성했는지 오답이 나왔고, 발상의 전환을 해서 소수가 나오면 해당 수(i)의 모든 배수를 대상으로 미리 (i-1/i)를 곱하는 형태로 구현했더니 기존 시간에 비해 터무니없이 빠르게 정답을 구할 수 있었다.
51번 이후에는 문제들은 이해되고 해결방안을 구현 가능하지만 극심한 성능문제가 발생하는 경우가 많이 나오고 있다. 단순 알고리즘 구현보다는 정수론 같은 수학을 이해하고 그것을 기반으로 효율적인 알고리즘 구현이 필요한 상황이 나오고 있어서, 수학공부까지 하면서 파이썬 공부를 위해 오일러 프로젝트를 계속 할 것인지 고민하는 상황이 계속 나오고 있는 것 같다.
Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal tonwhich are relatively prime ton. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6. The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.
Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
Find the value ofn, 1 <n< 107, for which φ(n) is a permutation ofnand the ration/φ(n) produces a minimum.
(파이 함수라고도 부르는) 오일러의 토션트 함수 φ(n)은 n에 대해 상대적으로 소수인 n보다 작거나 같은 양의 정수를 결정하는 함수이다. 예를 들어, 1, 2, 4, 5, 7, 8은 9보다 작으면서 9에 대해서는 소수이므로 φ(9)=6이다.
문제가 그렇게 까다롭게 보이지는 않았는데, 50번 이후 문제 대부분이 그렇듯이 1~1천만까지 있는 숫자 중에서 답을 구해야 되는 덕분에 실행시간이 많이 필요하므로, 통상적인 방법으로 시간을 들여 답을 구하거나, 숨어 있는 수학이론을 찾아 빠른 시간 내에 답을 구해야 한다는 것이 실제 문제였다.
69번 문제를 생각해보면, n/φ(n)가 최대인 경우는 n이 크면서, φ(n)이 작은 경우를 구하기 위해, 소수인 약수가 가장 많은 경우를 구해서 해결했다. 70번 문제는 정반대인 n/φ(n)이 최소인 경우를 묻고 있으므로, n이 작으면서 φ(n)이 큰 경우이며, 이 경우를 충족하려면 2개의 소수가 약수인 경우가 될 것이다 (자신이 소수인 경우는 1 작은 수가 순열이 되지 않아 제외). 2개의 소수가 편차가 작을수록 값이 작아질 것이기 때문에 √10000000(천만, 107)인 3300 전후의 두 숫자가 조건을 만족할 것으로 추정되었는데, 자신이 없어서 천~만 사이의 두 소수를 곱해서 나오는 값(n)의 φ(n)이 n의 순열이 되면서 n/φ(n)이 최소인 값을 구하는 과정을 통해 답을 구할 수 있었다.
처음에는 φ(n)을 구하면 순열을 만들어서 n이 있는지 확인했는데, n과 φ(n)을 리스트로 만들어 정렬해서 두 값이 같은지 비교하는 것이 훨씬 빠르게 순열 여부를 확인할 수 있었다.
