[BOJ] 11727번: 2×n 타일링 2

https://www.acmicpc.net/problem/11727


11726번 문제와 비교했을 때 2×2 타일이 하나 추가되었습니다. 그렇지만 풀이 자체는 비슷하게 점화식을 이끌어내면 됩니다. 2×n 직사각형에서 (1,1) 위치를 생각해보면 이 위치는 1×2 타일로 덮이거나 2×1 타일로 덮이거나 2×2 타일로 덮입니다. 1×2로 덮이게 될 경우에는 (2, 1) 위치에는 반드시 1×2 타일이 와야하므로 2×(n-2) 타일을 까는 경우의 수가 됩니다.


2×1로 덮이게 될 경우에는 첫 열이 처리되고 이제 남은 2×(n-1) 타일을 까는 경우의 수가 됩니다. 마지막으로 2×2로 덮이게 될 경우에는 두 열이 처리되고 남은 2×(n-2) 타일을 까는 경우의 수가 됩니다.그러므로 D[n] = D[n-1]+2*D[n-2]임을 알 수 있습니다.


https://github.com/encrypted-def/BOJ/blob/master/11727.cpp

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 11052번: 붕어빵 판매하기  (0) 2018.01.01
[BOJ] 2133번: 타일 채우기  (0) 2018.01.01
[BOJ] 2294번: 동전 2  (0) 2018.01.01
[BOJ] 11053번: 가장 긴 증가하는 부분 수열  (0) 2018.01.01
[BOJ] 1697번: 숨바꼭질  (9) 2018.01.01
[BOJ] 9465번: Stickers  (0) 2018.01.01
  Comments