[코딩으로 풀어보기] 문제적 남자 : 브레인 유랑단 13회, 신비로운 문제

※ 정답과 풀이가 포함된 스포일러가 있습니다.

[ 문제적 남자 : 브레인 유랑단 13회, 역대급 신비로운 문제]

문제

와, 이번 문제는 정말 신기하고 신비로웠다.

서로 전혀 다른 두 풀이가 같은 답을 만들어냈다.

우선 두 정사각형 모두, 가로줄과 세로줄, 대각선줄의 합이 같도록 수를 채워야했는데 그 답으로 위와 같이 채워진 것이다.

규칙 (문제의 정답)

왼쪽 사각형에 있는 한 칸의 수를 영어로 적었을 때, 그 단어의 길이가 오른쪽 사각형의 같은 칸에 적혀 있는 것이다.

그러면서 모든 줄의 합이 같게 유지된 것이다.

오현민은 등차수열로 접근해서 왼쪽 사각형을 풀고, 오른쪽에서 가능한 모든 경우의 수를 추린 후 정답을 찾았다.

여기서 나는 의문이 생겼다.

그럼, 이런 (두) 사각형은 얼마나 더 있을까?

탐색

1부터 99까지의 수로 3x3 사각형 칸을 채우기로 하고, 우리가 원하는 사각형을 찾아보도록 하자.

먼저, 모든 가로줄과 세로줄, 그리고 대각선줄의 합이 같도록 하려면 수의 배치가 어떻게 되어야 할까?

단순하게 생각해서 모든 칸에 1~99의 수를 하나씩 채운다고 생각해보면... 99개 중 9개를 뽑는 경우의 수만큼 해봐야한다.

즉, \(_{99}C_{9} = 1,731,030,945,644\) 이다. 이 정도면 빨라도 3~4시간 정도는 기다려야 결과가 나온다.

경우를 추려보자. 첫 줄의 합이 모든 줄에서의 합과도 같아야한다. 아래 그림과 같이 4개의 칸을 \(a,~b,~c,~d\) 로 고정한다면 다른 칸도 채워지지 않을까?

왼쪽 상단을 (1, 1), 그 오른쪽 칸을 (1, 2) 이라고 할 때, 아래와 같이 채울 수 있다.

모든 줄에서 같아야 하는 합을 \(S = a + b + c\) 라 하자. 그럼 첫 번째 열에서 (3, 1)칸(수식에서는 \(a_{3,1}\))은 \(S = a + d + a_{3,1}\) 이 되어야 하므로, \(a_{3,1} = S - a - d = (a + b + c) - a - d = b + c - d\) 로 전개된다.

나머지 칸에 대해서도 행/열로 두 연립방정식을 만들고 식을 전개하면 각 칸의 식을 채울 수 있다.

이제 \(a,~b,~c,~d\)만 정해서 모든 줄의 합이 같은 사각형을 바로 만들 수 있다.

(자세한 것은 코드에)

이렇게 사각형을 하나 만들고, 그 사각형들의 각 칸을 영어로 읽었을 때 그 길이로 다른 사각형을 하나 만든다.

다른 사각형에서 등장하는 모든 줄이 합이 일치하는 지를 확인한다.

(중복된 수가 있거나, 음수가 나오거나, 100보다 큰 수가 나오는 것은 제외하였다.)

\(a,~b,~c,~d\)를 각각 1부터 99까지 하나씩 집어넣어보면서, 만들 수 있는 모든 사각형를 확인해보면 된다.

결론

정말 신비롭게도, 경우의 수는 정답과 같이 "단 하나"만 가능했다.

이쯤되면 문제를 어떻게 만든 건지 궁금해진다. 대단하다.

100 이상의 수를 하지 않은 이유는, 코드 실행 시간이 너무 길어지기도 하고, 100은 영어 단어로 "one hundred" 라서 뭔가 한 단어처럼 되지 못한 느낌이라 그냥 뺐다. (하지만 이미 twenty + two 형태로 문제를 풀었음...)

코드

코드에서는 51번 줄에 MAXN = 100 이라 시간이 좀 걸린다. 문제의 정답은 15초쯤 지나면 나오니 실행해봐도 좋다.

정답 케이스는 \(a=5,~b=22,~c=18,~d=28\) 이다.

같은 수들이 칸 위치만 바뀌는 배치는 출력에서 제외했다.