[문제적 남자] 반드시 한 개의 숫자를 포함하도록 사각형으로 분할하라

1. Question

2. Approach

4각형 분할 문제다.

이 문제의 핵심은 칸을 채울 수 있는 숫자가 적은 칸부터 공략해나가는 것이 핵심이다.

먼저 가장 첫 칸을 살펴보자.

0, 0을 채울 수 있는 숫자는 체크 표시한 3개의 숫자 뿐이다. 먼저 가장 숫자가 큰 9부터 접근하자.

뭔가 처음부터 막대를 길게 잡으면 공간 낭비가 심할 것 같은 느낌이든다. 당장은 3 by 3으로 접근해보자.

이 경우, 다시 빗금친 부분을 채우려면 무조건 아래의 6을 사용해야 한다.

다시, 아래 칸의 강제성에 의해 4를 2 by 2로 채운다.

그런데, 새로 빗금친 칸을 살펴보면, 이 칸을 채울 수 있는 방법이 존재하지 않는다. 따라서 맨 처음 9를 채우는 가정은 틀렸다.

이제 문제가 되는 칸을 커버하기 위해, 3 by 3 칸을 한칸 내리자. 이에따라, 제일 윗 칸에 8이 자동적으로 할당된다.

여기서, 6을 아까처럼 길에 아래로 늘이면, 그 아래의 4가 강제된다. 또한 2열의 8의 모양 역시 강제된다.

이 경우에 다시, 빗금친 칸이 커버되지 않는다. 따라서, 이 가정도 틀렸다.

이번엔 3 by 3을 오른쪽으로 한 칸 이동해보자. 그리고 아까랑 비슷하게 8로 윗쪽을 채워보자.

이에 따라, 6이 강제되고 밑에 4를 어떻게 배치할지 생각해보자.

가장 먼저, 걸리적 거리지 않게 아래로 길게 붙여보자.

빗금된 칸을 채우기 위해 6이 강제되며. 동시에, 2열의 8의 모양이 강제되고, 그에 이어 4열의 9의 모양도 강제된다.

이 때 문제가 생기는데, 체크한 8을 배치할 수가 없다. 따라서 4를 아래로 길게 배치하는 가정은 틀렸다.

이제 4를 2 by 2로 배치해보자.

이 경우에 강제로 배치되는 숫자들이 꽤 많다.

7열의 6을 살펴보면 세로로 길게 놓거나, 3 by 2로 놓는 2 경우의 수 밖에 없다.

세로로 놓는 것을 살펴보면,

오목하게 들어간 부분에 갖힌 4가 강제되고, 체크한 8을 배치할 수 없게 된다. 따라서 6은 3 by 2로 두는 것이 맞다.

6을 3 by 2로 두고 바로 오른쪽에 8을 살펴보면, 빗금친 부분을 채우기 위해선, 4 by 2나 2 by 4 둘 중 하나가 되어야 한다.

먼저, 4 by 2부터 살펴보면,

10을 배치할 수가 없다. 8을 2 by 4로 배치하자. 이 후에 10을 잘 보면, 매우 비효율적이지만 세로로 하는 것이 가능은 하다.

하지만 빗금친 부분을 채울 수가 없다. 그냥 얌전히 5 by 2로 채우자. 여기까지 왔으면 거의 다 끝났다고 봐도 된다. 10의 오른쪽의 8과 6이 강제되고, 그에 따라, 위쪽에 4와 6이 또 강제된다.

여기서, 빗금친 부분을 커버할 수 있는게 8밖에 없으므로 8도 2 by 4로 고정이다.

동시에 오른쪽에 6도 고정되고

나머지는 그냥 브루트 포스로 대입하다보면, 정답이 나온다.