문제설명
가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하여라.
입력조건
- 첫째 줄에 N이 주어진다.(1 <= N <= 1,000)
출력조건
- 첫째 줄에 2 X N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.
개미전사 문제와 거의 비슷하다.
개미전사의 d[n]은 최대로 털 수 있는 식량들의 최댓값
여기서 d[n]은 바닥을 채울 수 있는 경우의 수
d[1] = 1, d[2] = 3 으로 첫번째 값과 두번째 값을 알 수 있다.
d[3]의 경우부터 2가지 경우의 수로 나뉜다.
d[2]에서 가로가 1cm 세로가 2cm인 바닥을 덮는 하나의 경우가 있고
d[1]에서 가로가 2cm 세로가 1cm인 바닥 2개로 덮고 2cm 2cm인 바닥을 덮는 2가지 경우가 있다.
여기서 가로가 1cm 세로가 2cm인 바닥 2개로 덮는 경우를 뺀 이유는 이미 d[2]에서 세로로 놓는 경우를 고려했기때문이다.
최종적으로 d[i] = d[i-2]
나는 점화식이 (d[i-1] + 1) + (d[i-2] + 2) 로 만들어질거라 생각했는데
이렇게 되면 d[3] = 4 + 3 = 7이 된다.
d[3]이 d[1]만 고려했을 때 d[2] + 1이 될 수 있는가?
d[2]에서 1가지 경우의 수가 추가(총 4가지 경우)가 되는 것이 아니다!
전체적으로 보자면 d[2]의 경우의수를 그대로 사용하는 거다.
d[1]의 경우의 수 2가지를 그대로 사용하는 것도 마찬가지다.
