randomgns   1년 전

저는 DP에 취약합니다. 맨날 점화식 세우라는데 수학을 몰라서 그거 만드는데 한세월이에요.

그래서 이런 문제를 풀 때 보통 몇 가지의 테스트 케이스로부터 패턴을 추출해서 만드는데, 막상 그 식이 물리적으로 이해가 안 갈 때가 더 많습니다. 저만 그런지 모르겠는데 논문에 있는 수식들보다 더 안와닿을때가 많아요.

결국 점화식 자체를 물리적으로 이해하지 못하면 제대로 이해한게 아니라고 생각해가지고 그림을 그리게 됩니다. 이 글은 저만큼 이런 문제에 접근하기 어려우신 분들을 위해 문제 풀이 과정에서 그린 그림을 설명하는 겸 스스로 머리에 박아넣으려고 쓰는 글입니다.

---

우선 문제 자체를 n=1부터 250까지 너비가 1씩 오른쪽으로 증가하는 사각형 틀로 보겠습니다. 그리고 메모이제이션을 위한 테이블은 사각형 틀의 가장 오른쪽 끝을 각각 정사각형(2x2), 가로막대(2x1), 세로막대(1x2)로 놓는 경우를 기록하도록 구성하겠습니다. 이렇게 구성하는건 처음부터 떠올린건 아니고, 아래처럼 그림을 그리다가 떠올랐습니다.

preview

preview

이처럼 n=6까지 약간의 노가다를 해보면 어느정도 감이 오기 시작합니다. 보통 나오는 숫자들을 나열해보면 뭔가 패턴이 보일테니 결과를 전부 모아봅니다.

preview


그리고 눈썰미가 좋으신 분들은 바로 아래와 같은 패턴이 보이실겁니다.

preview

n번째에서 가장 오른쪽에 정사각형 또는 가로막대를 놓는 경우의 수는 n-1번째에서 가장 오른쪽에 세로막대를 놓는 경우의 수와 같고, n번째에서 가장 오른쪽에 세로막대를 놓는 경우의 수는 n-1번째의 합과 같습니다. 마침 정사각형과 가로막대를 놓는 경우의 수가 동일하기 때문에 실제 구현에서는 테이블에서 정보를 하나 제거해도 되겠네요. 이제 패턴이 보이니까 이걸 기반으로 점화식을 세우시면 됩니다.

그런데 저는 머리가 나쁘다보니 점화식이 중요한게 아니라 이게 왜 되는지를 물리적으로 이해하고 싶습니다. 세로막대를 놓을수 있는 경우가 n-1번째의 합과 동일한 것은 바로 이해가 되는데, 왜 정사각형을 놓는 경우와 가로막대를 놓는 경우가 n-1번째에서 세로막대를 놓는 경우와 동일해질까요? 그림을 쳐다보며 발견한 규칙은 다음과 같습니다.

preview

이쯤 되면 해석을 정답에 끼워 맞추는건지 진짜로 이 해석이 맞는건지 애매하긴 하지만, 어쨌든 n-1번째에서 세로막대를 가장 오른쪽에 놓는 경우를 모아서 n번째에서 세로막대를 제거하고 정사각형 또는 가로막대를 놓는 경우의 수만 계산하면 됩니다.

---

마지막으로 문제에 "n=0이면 채워진 것으로 본다."와 같은 문구 추가가 필요해보여서 건의드립니다. 질문 글에도 보니까 여러가지 의견들이 있던데, 개인적으로도 "2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오."라는 문장이 있음에도 불구하고 채울 수 있다라고 이야기 하는 것 자체가 와닿지 않았기에 의견 한 표 드립니다.

yukariko   1년 전

"왜 정사각형을 놓는 경우와 가로막대를 놓는 경우가 n-1번째에서 세로막대를 놓는 경우와 동일해질까요?"

적으신 글에 힌트가 있습니다.

"n번째에서 가장 오른쪽에 세로막대를 놓는 경우의 수는 n-1번째의 합과 같습니다."

즉, '정사각형을 놓는 경우와 가로막대를 놓는 경우는 n-2번째의 합'과 같기 때문입니다.

그리고 그 이유는 n-2칸이 채워진 상태에서 남은 2칸을 정사각형으로 채우는 방법의 수는 하나이기 때문입니다.

댓글을 작성하려면 로그인해야 합니다.