[백준] 11726번 타일 채우기

예전에 취업 준비 하면서 공부 했을때도 잘 못했던 DP 문제를 공부하기 위해 DP를 다시 열었다..

근데 여전히 하~나도 예전보다 어쩌면 더 잘 모르겠다..

그래서 쉬운거?부터 천천히 공부해봐야지!

 

문제입니다!

 

문제에 대해 하나하나 채워보았다.

채우게 되면 위와 같은 모양이 되는데, 여기에는 규칙이 있다.

 

2x3의 타일을 채우는 방법을 전부 나열하게 되면, 아래와 모양이 되는데 이것은 1번에 2개의 타일을 더하는 방법과 2번에 1개의 타일을 더하는 방법으로 표현 할 수 있다.

여기서 첫번째 세번째 모양이 같아서 이 것을 제외한 3가지 방법이 2x3을 채우는 방법의 개수가 된다.

 

그럼 이제 규칙성을 눈치챘을까?

나는 이때도 몰라서 한 번 더 채워보았다.

 

2x4를 채우는 방법을 전부 나열하게 되면, 아래와 같은 모양이 된다.

이것은 3번을 채우는 방법에 1개의 타일을 더하는 방법, 2개의 블록에 2개의 타일을 더하는 방법에서 겹치는 것을 빼주면 된다.

 

여기서 포인트는

두개의 블록을 더할때, 세로로 세워진 블록을 더하는 경우는 생각해주지 않아도 된다는 것이다. 왜냐하면 하나의 블록은 세워져 있기 때문에 이미 그 경우의 수를 생각해 주었기 때문이다.

 

따라서 방법을 정리하게 되면,

1개를 더하는 경우 -> 1개 전

2개를 더하는 경우 -> 2개 전

의 개수와 같게 되어 현재 n개의 경우의 수는 T[n] = T[n-1] + T[n-2] 가 된다.

 

따라서 구현은 피보나치와 비슷하게 된다.

 

내가 구현한 소스코드는 아래와 같다.

 

으어.. 처음에는 결과에 10007을 나누기를 해주었는데, 계속 런타임 에러가 나서 함수에서 해주는 것으로 바꿔주었더니 PASS했다..! 왜그런지 아시는분은 댓글로 알려주세요 ㅠ_ㅠ

어려운 DP.. 다음엔 찾아내리라 규칙성.... 부드루븓ㄹ

 

끘~~!