세줄로 타일깔기

저희 원에 다니는 학생이 여기서 다음과 같은 문제를 풀었는데...

수학학원에서 똑같은 문제를 풀었다면서 문제 푼 방식을 공유해 주어서 올려 봅니다.^^

문제

바닥이 가로 30칸, 세로 3칸으로 이루어졌을 때, 가로 1칸, 세로 2칸(회전 가능하다)의 타일을 이용해 타일을 까는 경우의 수를 계산하자.

우리 원에서 푼 방식

이런 방식으로 공식을 추출하면 다음과 같은 로직이 나오네요.

dt[0]=1; dt[2]=3; for(i=4;i<=n;i+=2) {      dt[i] =  dt[i-2] * 3; //바로 이전의 타일의 경우 * 3      for(j=i-4;j>=0;j-=2) dt[i] += dt[j] * 2; }

이런 방식으로 프로그래밍 코딩을 하면 이 규칙만으로도 충분히 구할 수가 있거든요...

그런데 수학시간에 이 문제를 n=30 인 경우를 구하는 문제가 나왔나 보네요.^^

이렇게 손으로 계산하다가는 계산 할 수가 없더라구요.

수학시간에 배운 공식을 학생이 공유해 주어서 같이 공유해 봅니다.^^

학생이 적어온 노트입니다.^^

처음에 3*2n 을 채우는 가짓수 = Pn 으로 가정합니다. 2n으로 두는 이유는 짝수만 가능하기 때문입니다.

T를 기준으로 세로를 An 가지라 가정합니다.

T를 기준으로 가로 형식으로 하면 두가지 형태로 분기가 됩니다.

첫번째 형태로 분기 되는 경우는 Pn-1 가지가 됩니다.

두번째 형태로 분기가 되는 경우는 An 가지가 동일하게 됩니다.

따라서 Pn = 2An + Pn-1 의 공식이 성립하게 됩니다.

다시 An 을 확인해 보면

위의 그림과 같이 두가지 형태로 분기가 됩니다.

위의 경우는 Pn-1 가지가 되고...

아래와 같은 형태로 분기를 하면 An-1 형태가 됩니다.

따라서 An = Pn-1 + An-1 이 성립하게 되는 것이죠.

다시 Pn=2An + Pn-1 을 Pn = 2(Pn-1 + An-1) 로 만들수가 있고

이것을 2An-1 = Pn-1 - Pn-2 로 풀어 낼수가 있습니다.

따라서 Pn-Pn-1 = 2An 

                     = 2Pn-1 + 2An-1

                     = 2Pn-1 + Pn-1 - Pn-2

Pn = 4Pn-1 - Pn-2 라는 공식을 얻게 되네요.

이러한 공식을 얻게 되면 손으로 표를 만들어 풀수도 있을것 같습니다.^^