오일러 프로젝트 68 번은 특별한 마방진에 관한 문제이다. 문제에 그림이 등장하기 때문인지 (한국어 사이트 기준으로) 풀이 수도 많지 않고, 포럼에 등록된 답변도 많지 않지만, 문제의 조건을 유심히 살펴보면 시험해야 하는 경우의 수를 많이 줄일 수 있고, 코드의 실행 시간 역시 그리 길지 않은 평이한 난이도를 가지고 있다.
아래와 같이 바방진과 유사한 성질을 가진 도형이 있습니다. 1부터 6까지의 숫자가 한 번씩만 사용되었고, 선을 따라 합을 구하면 항상 9가 됩니다.
바깥으로 뻗친 가지 중에서 가장 숫자가 낮은 것부터 시작해서 직선들을 시계 방향으로 돌아가며 나열하면, 도형의 모양을 숫자로 나타낼 수 있습니다. 위 그림의 예를 들면 4,3,2; 6,2,1; 5,1,3 이 됩니다.
위 도형으로는 네 가지 다른 합계를 가지도록 배열할 수 있는데, 다음과 같은 여덟개의 풀이가 존재합니다.
- 합계 9 : 4,2,3; 5,3,1; 6,1,2
- 합계 9 : 4,3,2; 6,2,1; 5,1,3
- 합계 10 : 2,3,5; 4,5,1; 6,1,3
- 합계 10 : 2,5,3; 6,3,1; 4,1,5
- 합계 11 : 1,4,6; 3,6,2; 5,2,4
- 합계 11 : 1,6,4; 5,4,2; 3,2,6
- 합계 12 : 1,5,6; 2,6,4; 3,4,5
- 합계 12 : 1,6,5; 3,5,4; 2,4,6
하나의 풀이에 대해서 각 숫자를 모두 이어 붙이면 9자리의 숫자를 만들 수 있고, 그 중에서 가장 큰 것은 432621513이 됩니다.
이제 아래와 같은 도형에다 마방진의 성질을 가지도록 1부터 10까지의 숫자를 채우고, 같은 방식으로 풀이 숫자를 이어붙이면 16자리 혹은 17자리의 숫자가 만들어집니다. 이 때, 16자리 숫자 중에서 가장 큰 것은 무엇입니까?
(http://euler.synap.co.kr/prob_detail.php?id=68)
접근
그림에 지레 겁부터 먹지말고 우선 왼쪽의 그림을 보자. 10개의 칸에 A~I까지 이름을 붙인다. 이 때 A~I 까지의 글자에는 1~10까지의 숫자가 들어갈 수 있다. 이 도형의 5개의 변의 숫자의 합을 모두 더해보자.
(A + F + G) + (B + G + H) + (C + H + I ) + (D + I + J) + (E + J + F) 가 되어, 안쪽 오각형의 꼭지점에 해당하는 값들은 두 번씩 더해져서 (A + B + C + D + E) + 2(F + G + H + I + J)가 된다. 이 때 마방진의 특성상 모든 변의 길이가 같아야 하므로 총합을 5로 나눈 값이 한 변의 합이된다.
문제의 조건에서는 16자리 혹은 17자리의 숫자가 만들어질 수 있다고 했는데, 오각형의 꼭지점에 10이 오는 경우에는 숫자 2개짜리 수가 2번 들어므로 자리수가 많아질 것이다. 우리가 구하고자 하는 것은 16자리 숫자이므로, 10은 외곽에 위치한다. 그리고 모두 이어붙인 수가 커야 하니, 높은 숫자가 맨 앞에 올 수 있으려면 결국 6, 7, 8, 9, 10 이 위치야 어쨌든 간에 바깥에 위치해야 한다. (즉 ,ABCDE는 순서는 모르지만 6,7,8,9,10이다. 그러면 남은 FGHIJ는 1,2,3,4,5가 된다.
따라서 한 변의 길이는 ((6+7+8+9+10) + 2(1+2+3+4+5)) / 5 = 14로 계산된다.
그리고 한가지 추가적인 힌트로, 숫자를 이어붙일 때는 외곽에 있는 원 중에서 숫자가 가장 작은 것부터 시계방향으로 만들어나간다고 했다. 외곽의 숫자 5개가 6, 7, 8, 9, 10 이므로 위 그림에서 A 칸에는 항상 6이 온다고 고정한 후, 나머지 칸들을 채워나가도록 하자.
그러면 다음과 같은 조건들을 세울 수 있게 된다.
- 10개의 숫자를 리스트로 세워서 각 칸에 넣는다고 하고, 칸 A ~ J 까지는 0 ~ 9 까지의 인덱스로 나타낼 수 있을 것이다. 이 때, 각 변을 구성하는 인덱스의 순서쌍은 각각 다음과 같다.
- (0, 5, 6)
- (1, 6, 7)
- (2, 7, 8)
- (3, 8, 9)
- (4, 9, 5)
- 각 변에 오는 숫자들의 합은 모두 14가 되어야 한다.
- 외곽의 A를 6으로 고정하면, 외곽의 숫자칸을 채우는 방법은 4원소의 순열, 즉 4! 가지이다.
- 각각의 외곽 배치 방법에 대해서 내곽의 숫자칸을 채우는 방법은 5!가지가 있다.
- 이들 조합에 대해서 각 변의 합이 14가 되는 케이스를 검사하고, 1.에서 정의한 순서대로 숫자를 이어 붙여서 해의 집합을 구한다.
- 그 중에서 가장 큰 값을 얻는다.
Swift 풀이
숫자들을 순열로 세워야 하므로, permutations에 해당하는 함수 혹은 제너레이터가 필요한데, 이는 이미 만들어 본 적 있다.
func factorial(_ n:Int) -> Int {
guard n > 1 else { return 1 }
return (2...n).reduce(1, *)
}
func permutations<T>(of arr: [T], at n: Int) -> [T] {
var xs = arr
let n = n % factorial(arr.count)
if n == 0 { return arr }
let l = factorial(xs.count - 1)
let (q, r) = (n / l, n % l)
let a = xs.remove(at: q)
return [a] + permuatations(of: xs, at: r)
}그외에는 위 해설의 내용대로 코딩하면 된다. 수행시간은 30ms 정도.
let edges = [[0,5,6], [1,6,7], [2,7,8],
[3,8,9], [4,9,5]]
var result = Set<String>()
for i in 0..<(factorial(4)) { // 6을 제외한 나머지들을 줄세워본다.
let a = [6] + permutations(of: [7,8,9,10], at: i)
// 오각형의 꼭지점에 숫자들을 배치해본다.
inner: for j in 0..<(factorial(5)) {
// 하나의 경우에 대해서, 각 변의 합이 14인지 판단한다.
let b = permutations(of:[1,2,3,4,5], at: j)
var temp = [String]()
for edge in edges {
/// 실패하는 경우가 생기면 이번 판은 건너뛴다.
if (edge.map{ number[$0] }.reduce(0, +)) != 14 {
continue inner
} else {
temp.append(edge.map{ "\(numbers[$0])" }
.joined(separator: ""))
}
}
/// 모든 변의 합이 14이면, A위치부터 시계방향으로 연결된 숫자들의 모음을 다시 연결해서
/// 결과에 추가한다.
result.insert(temp.joined(separated: ""))
}
}
/// 추가된 결과를 모두 정수로 변환하고 가장 큰 값을 출력한다.
print(result.flatMap{ Int($0) }.max() ?? 0) /// 31msPython 풀이
파이썬 풀이 역시 동일한 알고리듬이나, 여기서는 튜플로 만들어지는 순열의 결과를 각각 리스트로 만들어서 결합하지 않고 어떻게 하나의 시퀀스로 엮어내는 테크닉을 소개한다. 또한 for 루프를 도중에 빠져나오게 되는 경우에 temp 의 개수를 체크할 필요 없이 else 블럭을 써서 처리하는 방법도 눈여겨 보기 바란다.
from itertools import permutations
def e068():
edges = ((0,5,6),(1,6,7),(2,7,8),(3,8,9),(4,9,5))
result = set()
for x in permutations((7,8,9,10)):
for y in permutations((1,2,3,4,5)):
numbers = (6, *x, *y) ## 여러개의 튜플을 하나로 합치기
for edge in edges:
xs = [number[x] for x in egde]
if sum(xs) == 14:
temp.append(''.join(str(x) for x in xs))
else:
break
else: ## for ... else 는 break 없이 루프를 완료했을 때만 호출된다.
result.add(''.joined(temp))
print(max((int(x) for x in result))
%time e068() ## Wall time: 5ms