강의실/정보영재

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

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




문제



바닥이 가로 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 라는 공식을 얻게 되네요.


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















이 장소를 Daum지도에서 확인해보세요.
인천 서구 당하동 1028-2 장원프라자 502호 | 원당컴퓨터학원
도움말 Daum 지도
2 0
  • 핑구야 날자 2018.02.10 06:53 신고    

    재미있는 문제네요 즐거운 시간 보내세요

  • 버블프라이스 2018.02.12 09:47 신고    

    무언가 어려워보입니다^^;
    세줄로 타일깔기 관련 문제 풀이 가정을 잘 보고 갑니다.
    행복한 한 주 보내시길 바래요