ndb796
p.224. 바닥 공사 질문있습니다.
또 글이 길어질 것 같으니, 미리 질문부터 드리면:
질문: 바닥 공사 문제의 점화식을 도출하는 과정을 더 상세히 알고 싶습니다.
이 아래로는 왜 질문을 드리는지에 대한 내용입니다.
왼쪽부터 i -2까지 길이가 덮개로 이미 채워져 있으면 1 × 2 덮개 2개를 넣는 경우 혹은 2 × 2의 덮개 하나를 넣는 경우로 두 가지 경우가 존재한다. - p.224
3 가지 모양(1×2, 2×1, 2×2)의 덮개가 주어지고 2×2 칸이 주어진다면 빈칸을 채울 수 있는 경우의 수는 두 가지가 아니라 세 가지 입니다.
- 1×2 덮개 2장 사용
- 2×1 덮개 2장 사용
- 2×2 덮개 1장 사용
"왼쪽부터 i - 2까지 길이가 덮개로 이미 채워져 있으면" 덮개를 놓을 수 있는 경우는 위에서처럼, 세 가지 경우입니다.
책에서는 i - 2까지 덮개로 채워져 있을 때, 덮을 수 있는 경우의 수를 두 가지로 했음에도 불구하고, 제가 직접 그려가면서 검토한 바로는 점화식은 맞는 듯 합니다. 점화식을 세우기 전 문단에서도 "왼쪽부터 N - 2까지 길이가 덮개로 이미 채워져 있는 경우 덮개를 채우는 방법은 2가지 경우가 있다"고 적혀있는 걸로 보아 단순 오타는 아닐 듯 합니다.
점화식을 정의할 때, 바닥을 채울 수 있는 형태가 두 가지이기 때문에 a[i]를 a[i - 1] + a[i - 2] + a[i - 2]라고 해준 것이라면, 세 가지의 경우에는 a[i - 1] + a[i - 2] + a[i - 2] + a[i - 2]가 돼야 하는 것 같은데.. 이렇게 하면 틀린 답이 나옵니다. (아래에 i-1, i-2를 작게 쓸 줄 몰라서 괄호를 사용했습니다..) 따라서 이 경우의 수가 점화식을 세우는데 별다른 역할을 못 하는 건 아닌가 싶은 생각이 들었습니다.
제가 시뮬레이션을 했을 때는 이랬습니다.
빈칸의 길이가 2일 경우에는 3가지 형태로 놓을 수 있습니다. 이는 위에서 확인했고요, 빈칸의 길이가 3이 되면, 앞서 3가지 형태에서 우측에 1×2 덮개 하나를 놓는 경우와, 3가지 형태에서 좌측에 1×2 덮개를 놓는 경우, 이렇게 총 6개의 형태로 놓을 수 있습니다. 다만, 1×2 덮개 두 장을 나란히 놓은 경우에는 1×2 타일을 좌측에 놓든 놓든 동일하기 때문에 이 경우를 제외하고 5개의 경우가 됩니다. 빈칸의 길이가 4가 되면, 빈칸의 길이가 2였던 경우 놓을 수 있었던 3가지 경우의 수를 놓을 수 있는 칸이 두배가 되므로 9(3×3)가지 경우를 만들 수 있습니다. 그리고 좌우에 1×2 덮개를 놓은 상태에서 길이가 2일때 놓을 수 있었던 방식으로 덮개를 놓으면 3가지 경우가 추가됩니다. 그리해서 12가지 경우가 있으나, 이때에도 1×2 덮개 4장을 이용한 경우가 중복되므로 하나를 빼면 11개의 경우가 됩니다. 빈칸의 길이가 5인 경우도 직접 다 따져보고 21개의 경우가 정상적으로 나오는 것은 확인했습니다.
요약하자면 빈칸의 길이가 2~5인 경우는 제가 일일이 따져보고 점화식이 맞다는 걸 확인했습니다.
이렇게 따져보면서 "N - 2까지 길이가 덮개로 이미 채워져 있는 경우 덮개를 채울 수 있는 경우의 수"가 점화식을 세우는데 기준이 될 수 있는가 하는 의문이 생겼습니다. 오히려 N칸일 경우, N-1, N-2칸이었을 때는 놓지 못 했던 모양을 얼마나 놓을 수 있으며, 몇 개나 중복이 생기는지를 따져봐야 점화식이 나오는 거 아닐까 하는 생각이 들었습니다.
점화식을 도출하는 방법에 대해 조금더 상세한 설명을 부탁드리겠습니다.
안녕하세요, @backtony 님!
이번에도 좋은 질문 감사합니다.
말씀해주신 부분 또한 제가 교재에서 명확히 명시했어야 했는데, 설명이 부족했던 것 같습니다.
책에서는 다음과 같이 명시되어 있습니다.
① 왼쪽부터 i - 1까지 길이가 덮개로 이미 채워져 있으면 2 X 1의 덮개를 채우는 하나의 경우밖에 존재하지 않는다.
② 왼쪽부터 i - 2까지 길이가 덮개로 이미 채워져 있으면 1 X 2 덮개 2개를 넣는 경우, 혹은 2 X 2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다.
여기에서 말씀하신 대로 ②에서 2 X 1 덮개 2개를 넣는 경우를 고려하지 않는 이유는 ①에서 이미 해당 경우가 계산되었기(고려되었기) 때문입니다.
결과적으로 책에 적혀 있는 점화식을 통해, 중복을 제외한 고유한 경우들만 고려한 최적의 해를 도출하게 됩니다.
명쾌하지 못한 설명 때문에 어려움을 느끼신 것에 대해 죄송한 마음이 드네요. 나동빈 드림
