농 위키

PS 일지 (6)

마지막 수정 시각: 2023-04-19 15:30:13

얼마나 갈진 모르겠지만 OI Checklist 돌기를 시작했다. 일단 JOISC 쉬운 것부터 풀어보기...

BOJ 27206

항상 \(B_i, B_j, B_k\) 셋 중 가장 크기가 큰 두 개가 합에 포함된다는 것을 알 수 있다. 제일 작은 원소는 max 함수의 결과값이 될 수 없고, 제일 큰 수를 두 번 고르는거보단 제일 큰것, 다음으로 큰것을 고르는게 이득이기 때문.

그렇다면, 배열을 \(B_i\) 순서대로 정렬하고 생각해보자. \(B_i\)가 작은 것부터 볼 것이므로, 항상 해당 원소가 "B값이 빠지는" 원소라고 생각하고, 이것보다 \(B_i\)가 큰 두 개의 원소와 같이 고르는 것으로 문제를 바꿔 생각할 수 있다.

이렇게 생각할 경우, 나머지 원소들에 대해서는 \(A_i + B_i\) 값이 가장 작은 두 개를 고르는게 무조건 이득이다. 따라서 각 원소를 \(A_i + B_i\) 순으로 정렬한 set을 만들고, 현재 원소 + set의 첫 두 원소를 고르는 모든 케이스를 확인해주면 문제를 \(O(NlogN)\)에 해결할 수 있다.

BOJ 24947

\(Z\) 값이 가장 큰 원소 하나를 고정해놓고, \(Z\)가 이것보다 작은 원소들만 본다고 생각해보자. 이 원소들만 놓고 따졌을 때, \(X\) 값이 가장 큰 것과 \(Y\) 값이 가장 큰 것이 서로 다른 원소라면, 이 둘을 고르는게 무조건 최선이다. 만약 이 둘이 \(Z\) 값 가장 큰 원소 고른 것보다 \(X, Y\)가 작다면, 선택 가능한 방법이 없다. \(X\) 값이 가장 큰 것과 \(Y\) 값이 가장 큰 것이 서로 같은 원소라면, 이 원소는 답으로 고려될 수 없다. 따라서, 이 원소를 제거하고 같은 논리를 전개해도 된다.

이러한 논리를 어떤 \(Z\) 가 고정됐을 때 빠르게 수행할 수 있고, 새로운 원소가 추가됐을 때의 갱신도 빠르게 이루어질 수 있다면 전체 원소를 \(Z\)가 증가하는 순으로 정렬하고 가장 작은 것부터 순서대로 추가하면서 문제를 해결할 수 있다.

일단 이 방향으로 접근해보자. 봐야하는 원소 후보 목록에서, \(maxy_x\)를 \(X=x\)인 원소들 중 \(y\)가 가장 큰 값이라고 생각하자. 이렇게 할 경우, 어떤 원소 \(x, y\)가 고정됐을 때, 이 원소와 같이 고를 수 있는 원소 중 최선의 \(y\) 값은 \(maxy_1, maxy_2, \dots, maxy_{x-1}\)중 가장 큰 값이다(그리고 이 값이 \(y\)보다 작으면 해당 원소와 같이 고를 수 있는 경우가 없음을 뜻한다).

이러한 형태의 쿼리는 갱신까지 포함하여 세그먼트 트리로 \(O(logN)\)에 수행하게 만들 수 있다. 그리고 위 논리에 따라 어차피 만들 수 있는 \(x\) 최대, \(y\) 최대는 주어진 집합에서 고정이므로, 한 번 이 값을 구해둔 후 새롭게 추가되는 \((x, y)\)가 이 값을 어떻게 갱신해줄 수 있는지만 확인하면 된다. 새롭게 추가되는 \((x, y)\)에 대해, 이 원소와 같이 선택할 수 있는 \(y\)의 최대는 \(x\)값이 이것보다 작은 원소중 \(y\)가 가장 큰 값이다. 이러한 쿼리는 앞서 말한 방식을 이용해 세그먼트 트리로 \(O(logN)\)에 수행할 수 있다(y축도 같이 봐줘야 한다). 이렇게 새롭게 추가되는 \(x, y\)를 고려해서 최대치를 다시 갱신해줄 수 있으므로, 전체 시간복잡도 \(O(NlogN)\)에 문제를 해결할 수 있다.

BOJ 17682

맨 윗줄부터 좌우로 텐트를 채워나가는 경우를 생각해보자. 일단 한 줄에 세 개 이상의 텐트는 배치할 수 없다.

그리고 좌우로 두 개의 텐트를 배치할 경우, 이보다 아래 라인에서는 해당 텐트가 있는 것과 동일한 \(j\) 위치에는 텐트를 놓을 수 없다(텐트가 좌우, 상하에 모두 존재하게 되기 때문). 따라서, 좌우로 두 개를 배치할 경우 그 좌표들이 존재하지 않는다고 생각하고, 아랫줄의 좌우 길이 자체를 줄인 다음 문제를 해결해도 괜찮다.

하나의 텐트를 배치하는 경우를 생각해보자. 텐트가 딱 하나 놓여있는 지점들을 따로 관리하면, 아래쪽에서 텐트를 하나 배치하면서 위에 있는 한개짜리 텐트와 같이 매칭하는 경우를 따로 고려해줄 수 있다. base case에서는 한 개 짜리 텐트들마다 경우의 수가 4씩 있다고 생각하고 곱해주면 된다.

하나도 배치하지 않는 경우는 그냥 넘어가면 된다.

이런 식으로 접근하면서 가능한 경우의 수를 계산해주면, \(DP(one, width, height)\) 를 1개짜리 텐트 라인이 \(one\)개, 쓸 수 있는 너비가 \(width\), 높이가 \(height\)일 때 경우의 수 라고 두고 \(O(N^3)\)에 문제를 해결할 수 있다.

이 방법으로 Subtask 1은 해결할 수 있을 것이나, Subtask 2를 해결하기에는 너무 느리다. 좀 더 빠르게 해결할 수 있는 방법이 있는지 생각해보자. 결국 3차원으로 구성된 DP의 상태를 줄이지 않으면 답이 없으므로, DP 상태를 더 줄일 수 있는지 생각해보자. 너비나 높이를 없애긴 힘들테니 한 칸짜리 애들을 따로 처리할 수 있는지를 생각해보는게 좋을 것 같다.

이렇게 생각해보면, 한칸짜리 애들을 먼저 배치해서 배치할 수 있는 경우의 수를 센 후, 좌우로 두줄 혹은 상하로 두줄만 배치가능하다고 생각하고 \(DP(width - one, height - one)\)을 푸는 방법이 가능해보인다. 두줄만 배치하는 \(DP\)의 경우 맨 윗줄부터 한 줄을 골라 거기서 상하로 놓거나, 그 맨 윗줄에 좌우로 놓거나, 그 줄을 무시하고 넘어가거나의 경우로 분류하여 \(O(NM)\)에 푸는 식을 세울 수 있다.

한칸짜리 애들을 배치하는 경우의 수를 생각해보면, \(((w \cdot h) \cdot ((w-1) \cdot (h-1)) \cdot \dots \cdot ((w-one+1) \cdot (h-one+1))) / (one!) \) 형태로 식을 유도할 수 있다. 한칸짜리를 놓으면 그 칸의 상하, 좌우에는 다른 칸을 놓을 수 없기 때문. 이렇게 배치하고 순서는 중요하지 않으므로 \(one!\)으로 나눠주면 식이 성립하게 된다. 따라서, 이런 전처리도 \(O(N+M)\)시간에 끝내놓을 수 있으므로 전체 문제를 \(O(NM)\)에 해결할 수 있다.

BOJ 15456

선물을 받을 수 없는 소들은 항상 맨 뒤에 있는 연속한 \(K\)마리의 소들이다. 이 소보다 앞에서 계속 줄이 돌아가면 여기까지 차례가 오지 않기 때문.

이러한 소의 수 \(K\)를 고정했다고 생각해보자. 이 \(K\)마리의 소들이 전부 선물을 받을 수 없는지 확인할 수 있는 방법이 있을까? 일단, 전체 \(K\)마리 중에 마지막 \(K-1\)마리는 중요하지 않다. 어차피 마지막에서 \(K\)번째 위치의 소까지 못 받아야 이게 성립하기 때문. 따라서 마지막에서 \(K\)번째 위치에 있는 소가 선물을 받을 수 있는지 여부만 확인한다고 생각해보자.

\(K\)번째 소보다 뒤로 가는 소들은 전부 무시해도 되고, \(K\)번째 소보다 앞으로 오는 소들은 여러 번 그 과정을 반복하게 된다. 이 과정을 계속 시뮬레이션 하면 \(O(N^2)\)안에 파악할 수 있으나, 너무 느리다. 더 빠르게 체크할 수 있는 방법이 있을까? 맨 앞 \(N-K\)개 소들의 크기를 정렬해보자. 여기서 가장 작은 값부터 순서대로 \(K\)번째 소보다 뒤로 이동하게 되고, 뒤에서 \(K\)번째 소는 한칸씩 앞으로 오게 된다. 따라서 뒤로 이동하게 되는 소들을 하나씩 확인해주면 \(O(NlogN)\) 시간에 확인을 끝마칠 수 있고, 따라서 전체 시간복잡도 \(O(Nlog^2N)\) 시간에 문제를 해결할 수 있다.

Prompt412 Round 183

7/8 풀었다. 플레티넘 중위권 정도 난이도부터 푸는데 시간이 너무 오래 걸려서 항상 마지막 걸 못 풀게 된다. 여기서 내가 잘 푸는 유형이 나오면 8문제, 아니면 7문제를 푸는 듯. 유형 상관없이 다 어느 정도 이상 속도로 풀 수 있는 연습을 하면 대회 성적이 좋아지지않을까? 싶긴 하다.

C. BOJ 22232

문자열을 .을 기준으로 파일명과 확장자로 분리한 다음, 이걸 문제에 주어진 조건에 맞춰서 정렬해주면 된다.

D. BOJ 1469

\(N\) 제한이 작아서 가능한 모든 경우를 테스트해보면 된다. 각 수마다 그 수의 왼쪽 위치를 결정하면 오른쪽 위치도 같이 결정이 되므로, \(2N\) 사이즈 배열을 만든다음 각 수가 들어갈 위치를 정해주면서 백트래킹을 하면 문제를 풀 수 있다.

E. BOJ 23222

brute-force하게 풀면 된다. 이것도 제한이 8밖에 안돼서, 만들 수 있는 모든 도형을 만든 후 개수를 세주자. 뒤집거나 돌려서 만들 수 있는 걸 전부 같은 모양으로 취급하는 점 때문에 구현이 상당히 귀찮다.

F. BOJ 12909

좀 복잡하게 풀었는데 다른 분들 코드를 보니 더 간단한 DP 식이 있는 듯. 간단한 방법을 고민해서 정리해본다.

\(DP(node, edge)\)를 아직 부모가 정해지지 않은 노드수가 \(node\), 자식이 정해지지 않은 간선 수가 \(edge\)일 때 가능한 최댓값이라고 하자. 각 \(node\)들은 남은 간선을 하나 써서 다른 노드의 자식으로 들어가야하고(루트 제외), 동시에 그 노드 밑에 다른 노드를 얼마나 붙일지를 계산해서 \(edge\)를 더해주면 된다. 이게 가능한 모든 경우를 보면 되므로 \(O(N^3)\)에 문제를 해결할 수 있다.

G. BOJ 19559

모든 간선을 \(V_a\)와 \(V_b\)의 합이 \(c\)라는 공식으로 변환해서 생각해보자. 이렇게 하면 각 연결된 컴포넌트마다 \(V_k\)를 처음 탐색의 시작점 \(V_a\)에 대한 상대적인 계산식으로 표현할 수 있다. 이 때, 이분 그래프라면 모든 정점이 \(-V_a\) 혹은 \(V_a\) 에 상수를 더한 형태로 표현되고, 그게 아니라면 어떤 지점에서 \(V_a\)의 값이 하나로 결정되게 된다. 이 각 케이스들을 분류해서 모순이 생기는지 아닌지를 판단하고, 모순이 생기지 않는다면 \(V_a\)의 값을 적절히 정해주면 된다. \(V_a\)값이 하나로 결정되는 경우 그걸 쓰면 되고, 그렇지 않다면 삼분탐색을 통해 전체 합이 최소가 되는 \(V_a\)를 구해서 이를 바탕으로 나머지 값들도 다 정해주면 문제를 \(O(NlogN)\)에 해결할 수 있다. 삼분탐색 쓰는 부분이 좀 애매하다고 느꼈는데 혹시 안 쓰고 풀 수 있는 방법이 있는지 찾아봐야겠다.

Prompt412 Round 187

무난하게 7/8 풀었다. A번에서 이상하게 말린 것 + G를 아는 유형인데 빠르게 풀지 못한 두 가지가 아쉬웠다. H는 무슨 이상한 물리 문제 같음 + 시간 없음의 콤보로 제대로 읽어보지도 못했다.

A. BOJ 15830

문제가 어렵다기보다 실수 오차가 짜증나는 문제. 풀이 자체는 문제에 주어진 식대로 잘 시뮬레이션하면 되나, 속도를 기준으로 하면 안되고 시간을 기준으로 계산해야 AC가 나온다.

C. BOJ 12993

\(3^k\) 단위로만 이동하므로, 각 x, y 값은 3진법으로 표현했을 때 자릿수가 0 혹은 1로 표현된다. 또, 같은 자릿수가 모두 1 1 이거나 0 0 인 경우는 존재해서는 안 된다(한 단계에 한 축으로만 이동 가능하므로). 따라서 x, y 좌표를 모두 3진법으로 표현한 뒤 이 조건을 만족하는지 아닌지 체크해주면 풀린다.

D. BOJ 27396

쿼리가 들어올 때마다 일일히 문자열의 모든 문자를 바꿔주면 당연히 시간 초과가 난다. 문자의 개수 보다는 각 문자가 어떤 문자로 매핑되는지가 중요하므로, \(i\)번 문자가 현재 어떤 문자로 바뀌었는지 배열을 따로 관리하자. 바꾸는 쿼리가 들어오면 이 값만 갱신해준다. 문자의 개수는 최대 52개 이므로 이 과정은 아주 빠르게 수행가능하다.

E. BOJ 11214

각 도로가 각 도시와 쌍을 이뤄야 하므로, degree = 1인 간선들을 모두 그 끝 도시와 연결해준 후 간선을 제거하는 과정을 반복한다. 이 과정은 위상정렬 알고리즘과 거의 동일한 방식으로 수행할 수 있다.

이렇게 하고 나면 그래프에는 싸이클만 남는다. 정점의 개수 = 간선의 개수이므로 이 싸이클들은 모두 정확히 원형으로 구성된다. 싸이클 내부의 정점들은 아무거나 하나 잡고 돌면서 다음 정점으로 향하는 간선과 연결해주면 된다.

F. BOJ 1827

방문 가능한 모든 경우를 나열하고 각 경우에 대해 이동 거리를 계산하는 식으로 답을 구하는 가장 나이브한 방식으로 풀린다. 다만 구현이 상당히 귀찮다.

G. BOJ 25761

\(maxh_w\) 를 너비가 \(w\)일 때 가능한 한 크게 만들 수 있는 높이라고 하자. 고정된 한 축에서 칸마다 밑으로 뻗을 수 있는 최대 높이를 미리 계산해두자. 이제 이 값으로 이루어진 배열에서, 히스토그램에서 최대 직사각형을 구하는 알고리즘을 적용해서 해당 라인에서의 \(maxh_w\)를 \(O(NM)\)에 계산할 수 있다. \(maxh_w\)를 계산하면 각 쿼리는 \(O(1)\)에 해결 가능하므로, 전체 시간 복잡도 \(O(NM+ Q)\)에 문제를 해결할 수 있다.

Prompt412 Round 188

오랜만에 전부 푸는데 성공. 전반적으로 내가 잘 알고 익숙한 유형이었다. 요즘은 플래티넘 범위에서 어떤 문제가 나와도 안정적으로 빠르게 풀 수 있는 능력이 필요하지 않나 싶은 생각이 든다.

E. BOJ 25395

맨 처음 커넥티드 카로부터 연결 가능한 차들을 계속 이어주는 걸 반복하면 풀 수 있다. 이 때, 현재 연결된 커넥티드 카에서 연결 가능한 차들의 위치는 항상 연속한 구간으로 나타난다. 따라서, 현재 연결된 맨 왼쪽 끝 차와 맨 오른쪽 끝 차 포인터를 유지하면서, 구간이 확장될 때 이 포인터를 각각 왼쪽, 오른쪽 끝으로 당겨주며 구간을 갱신하는 걸 반복하면 \(O(N)\)에 문제를 해결할 수 있다.

F. BOJ 27470

랜덤 알고리즘으로 푼다는 생각을 하면 쉬운데 그 생각을 하기가 쉬운지는 잘 모르겠다. 만약 조건을 만족하는 집합이 존재한다고 가정해보자. 집합에서 아무 원소나 골랐을 때 그 원소를 포함하는 멋진 집합이 존재할 확률이 50%이상이 된다. 따라서, 아무 원소나 고르고 이 원소를 포함하는 멋진 집합이 있는지 체크해보는 과정을 30번 정도 반복했는데 한 번도 그런 집합이 안 나올 확률은 \(2^{-30}\) 정도가 된다. 그러니 랜덤하게 원소를 뽑고 조건을 만족하는게 있는지 체크하는 과정을 30번 정도 반복해서 그래도 없으면 그런 집합이 존재할 확률이 매우 낮으므로 NO, 아니면 YES를 찍으면 문제를 해결할 수 있다.

G. BOJ 2416

전형적인 2-SAT 문제로 환원할 수 있다. 각 스위치의 상태를 하나의 boolean 변수로 보고, 문과 연결된 두 스위치의 상태에 따라 문의 상태가 결정되는 것을 하나의 항으로 보면, 2-SAT 문제와 완전히 동일한 세팅이 된다. 그 다음은 그냥 2-SAT 문제를 해결하는 알고리즘을 가져와서 쓰면 풀린다.

H. BOJ 16881

푼지 오래돼서 풀이가 잘 기억이 안 난다. 좀 특이한 방식으로 그런디 수를 계산해야했던 것만 기억이 나는데... 나중에 다시 보고 한 번 정리해보는게 좋을 수도.

Prompt412 Round 191

무난하게 7/8 풀었다. G번을 풀이 얼개를 빨리 잡고도 한참 고생한게 제일 컸다. G를 빨리 풀었으면 H를 볼 여유가 좀 있었을 것 같은데..

F. BOJ 17036

매우 귀찮은 케이스워크 + 애드혹 문제. 일단 비교적 쉬운 최대 횟수부터 생각해보자. 전체 구간에서 한쪽 끝은 무조건 버려야하고, 나머지 중간에 있는 빈 칸은 다 하나씩 채워가면서 쓸 수 있기 때문에 양 끝 칸과 그 다음 칸 사이의 빈칸 간격이 제일 좁은 걸 전체 간격에서 빼주면 최대 횟수가 된다.

이제 최소 횟수를 구하는 방법만 찾으면 된다. 최소 횟수를 구성하는 어떤 구간 \(l\)부터 \(r\)까지가 있다고 생각해보자. 여기서, \(l\) 왼쪽, \(r\) 오른쪽 위치에 각각 반드시 소가 한 마리씩은 있는 경우를 생각해보자. 이런 구간 중에 최소 횟수인 어떤 구간을 잡으면, 이 구간의 \(l\) 위치에 항상 원래 소가 있다고 생각할 수 있다. 그렇지 않은 경우 \(l\)보다 왼쪽의 빈칸을 오른쪽으로 밀어서 동일한 개수를 맞추면서 \(l\) 위치에 항상 소가 한마리는 있게 만들 수 있기 때문이다. 이렇게 해놓고 보면, \(l\) 왼쪽, \(r\) 오른쪽에 항상 소가 있으므로 \(l\) 왼쪽의 소를 \(r\) 위치로 옮기면 무조건 빈 칸을 정확히 채워넣을 수 있다.

이게 불가능한 케이스는, \(l\) 왼쪽에만 소가 있거나 \(r\) 오른쪽에만 소가 있는 경우이다. \(l\) 왼쪽에만 소가 있는 경우든 오른쪽에만 소가 있는 경우든, 소가 2마리 이상인 경우 그 사이 구간을 원하는 위치로 잡아주면 위와 동일하게 항상 최소 횟수(중간에 있는 빈 칸 개수)만큼의 연산으로 해결이 가능하다. 따라서 구간 바깥에 소가 정확히 한마리만 남으며, \(r\) 위치에 소가 없는 경우만 문제가 된다. 이 때에는 구간 안에 속하는 소의 수가 \(n-1\) 마리이므로, 빈칸은 정확히 \(r\) 위치 한 군데에만 존재한다. 이 경우는 \(l\) 위치의 소를 \(r+1\) 로 옮기고 바깥의 소를 \(r\) 위치로 옮기는 경우가 최선이다. 따라서, 답이 1 더 필요하다.

이 경우들을 다 잘 분류해서 구현해주면 문제를 해결할 수 있다.

G. BOJ 16700

\(x\) 제한이 아주 작다는 것에 집중해보자. \(x\) 축에 존재하는 아직 1번 쿼리로 주어지는 사각형에 덮이지 않은 y 위치들을 \(live(x)\) 라는 set으로 관리한다고 생각해보자. 이제 1번 쿼리가 주어지면, 각 x 축에 대해 주어진 \(y1, y2\) 사이에 있는 \(y\) 좌표들을 set의 lower_bound, upper_bound를 이용해 순회하며 지워줄 수 있다. 한 번 방문한 y좌표는 바로 지워지므로 동일한 칸은 최대 한번만 방문한다. 따라서, 1번 쿼리는 모든 과정을 통틀어 amortized \(O(QX + XYlogY)\) 시간에 동작한다. 그리고, \(y\) 좌표를 지울 때 그 좌표에 상하 좌우에 있는 기존에 지워진 좌표와 한 집합으로 합쳐주면(union_find), 2번 쿼리는 단순히 두 칸이 같은 집합에 존재하는지 확인하는 것으로 해결할 수 있다. 이 과정은 유니온 파인드 자료구조 연산의 시간복잡도와 동일하므로 \(O(XY)\) 만큼의 시간이 걸린다. 따라서 전체 시간복잡도 \(O(Q(X+logXY)+ XYlogY)\) 시간에 문제를 해결할 수 있다.

Prompt412 Round 190

다른 일정이 있어 참가 못 했던 라운드의 맨 뒤 두 문제를 풀었다. 둘다 괜찮은 문제였다.

G. BOJ 11677

각 직원 \(x\)에 대해, 그 직원이 가장 빠르게 승진할 수 있는 타이밍을 \(l(x)\), 가장 늦게 승진할 수 있는 타이밍을 \(r(x)\)라고 하자. 어떤 승진 횟수 \(k\)에 대해, \(r(x) \le k\)면 이 직원은 무조건 승진한다. 또, \(k \lt l(x)\) 면 그 직원은 절대 승진할 수 없다. 즉, 모든 직원에 대해 \(l(x), r(x)\) 값을 계산해두면 문제에서 계산하고자 하는 값을 \(O(V)\) 시간에 해결할 수 있다.

각각의 정점에 대해 \(l(x), r(x)\) 값을 계산하는 과정을 생각해보자. \(l(x)\)는 나보다 먼저 승진해야 하는 모든 애들을 다 승진하고 나서 내가 승진하는 경우이므로, 나와 간선으로 연결된 내 앞 정점들의 개수가 된다. \(r(x)\)는 반대로, 나와 간선으로 연결된 내 뒷 정점들의 개수를 전체 정점 개수에서 빼준 것이 된다. 나보다 더 늦게 승진해야만 하는 애들을 제외하고 나머지를 모두 승진시킨다음 내가 승진하는 경우가 가장 늦게 승진하는 경우이기 때문이다.

즉, \(l(x), r(x)\) 는 전부 각각 DFS를 한번 수행하면서 조건을 만족하는 정점의 개수를 세주는 것으로 구할 수 있고, 따라서 각 정점마다 \(O(V+E)\) 만큼의 시간이 필요하다. 이 과정을 모든 정점에 대해 수행해주면 되므로 전체 시간복잡도는 \(O(V^2+VE)\)가 된다. \(V,E\) 제한이 작아서 충분히 문제를 해결할 수 있다.

H. BOJ 19568

15x15 크기의 직사각형에서, 사각형의 왼쪽 위는 \((0,0)\)으로 고정해놓고 오른쪽 아래를 어떤 \((x,y)\)로 지정한 사각형들만 이용해서 1부터 15x15 까지의 모든 수를 표현할 수 있는지 생각해보자.

이런게 가능하다면, 30x30 크기의 직사각형을 왼쪽 위에 15x15 크기의 사각형, 오른쪽 아래에 15x15 크기의 사각형 두 개로 분할한 후, 사각형의 한 점은 왼쪽 위 사각형, 사각형의 한 점은 오른쪽 아래 사각형에 두는 식으로 50000범위의 모든 수를 표현할 수 있다. 오른쪽 아래 사각형은 마찬가지로 1 ~ 15x15 까지의 수를 표현하게 두고, 왼쪽 위 사각형은 이 범위에 225를 곱해주면 225진법으로 왼쪽 위에서 한 자릿수, 오른쪽 아래에서 한 자릿수를 고르는 식으로 225x225 = 50625개의 수를 모두 표현할 수 있기 때문.

그리고 15x15 크기의 직사각형에서 1부터 15x15를 모두 표현하는 건 아래와 같은 방식으로 할 수 있다.

왼쪽 위 사각형은 이 사각형의 모든 칸에 225를 곱한 다음 상하 반전 좌우 반전해서 그려주면 문제의 조건을 만족하는 30x30 표를 만들 수 있다.