meme0724   1년 전

N이 홀수인 경우에는 '채울' 수 없잖아요?

그런다면 N이 홀수인 경우에는 경우의 수가 0, 즉 0을 출력해야 하는 건가요?

N이 짝수일 경우에는 제가 확실히 맞췄다고 생각하기에 질문 올려봅니다.

만약 홀수일 때 0을 출력하는 것이 맞다면 아래 코드에서 제가 tile함수를 잘못 정의했다는 뜻이 되는데

어디가 문제인지도 조언에 주시면 감사하겠습니다.

dudn134   1년 전

일단 식이 잘못 된거 같네요..

dudn134   1년 전

87c677070eaf6233a1755b15d21565d8.png


dudn134   1년 전

그리고 홀수일땐 0이 맞습니다

meme0724   1년 전

아직 어디가 잘못되었는지 잘 모르겠습니다.

return tile(2)*tile(n-2) + 2*tile(n-4); 이부분에 대해서 자세히 설명을 해 드리겠습니다.

3XN칸의 바닥을 채울 때의 경우의 수를 tile(n)이라고 정의합니다.

N=0일 때는 1가지라고 따로 하고, N=2일때는 3가지입니다. 이 두가지는 미리 정해놓습니다.

그런데 1X2 와 2X1의 타일로만 3XN칸의 바닥을 채우려면 반드시 3X2나 3X4칸이 만들어지게 되고 이들로만 타일을 채워야 합니다.

위의 그림은 3X4일때이고 3X2일 때는 다음 그림과 같이 되겠죠.

9618ace7956a44c51c8ce19270400f05.png

따라서 몇칸을 채워야 하든 간에 우선은 3X2 또는 3X4를 먼저 채워야 합니다.

3X2를 채우는 경우는 보다시피 3가지고 3X4를 채우는 경우는 3X2도 채워지는 경우를 제외하면 위의 2가지만 남는걸로 알고있습니다.

따라서 3XN칸을 채울때 3X2 먼저 채웠 때의 경우의 수는 tile(n-2)가지고 3X4 먼저 채웠을 때의 경우의 수는 tile(n-4)가 됩니다.

결국 tile(n) = 3*tile(n-2) + 2*tile(n-4)라는 식이 성립한다는게 제 생각입니다. (tile(2)=3)

음.... 제가 문제를 풀다가 틀리면 항상 어이없는 곳에서 실수를 하는데 이번에도 제가 미처 생각못한 부분이 있나요?

mrcamel   1년 전

3XN칸의 바닥을 채우려면 반드시 3X2나 3X4칸이 만들어지게 되고 이들로만 타일을 채워야 합니다.

라고 하셨는데

── ── ──

│ ── ── │

│ ── ── │

이런 경우도 있지 않을까요..

meme0724   1년 전

아하하하하하하하하하하

역시나 저의 생각에 실수가 있었던 거네요....

언제까지 해야 실수없는 코더가 될 수 있을까요.....

쨋든 저의 미숙함을 한 번 더 일깨워주셔서 감사합니다!!

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