[backjoon oj][Dynamic] 11726 - 2 X N 타일링

---

문제

- 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

예제 입력 1 : 2        예제 출력 1 : 2

예제 입력 2 : 9        예제 출력 2 : 55

---

(알고리즘 문제 공부를 처음 시작해 보는데, 유튜브로 백준님의 다이나믹 알고리즘 강의를 듣고 공부를 시작했당)

- 어떤 경우의 다음 결과가 정해져 있다면 그것까지 포함해서 하나의 경우로 친다. - 

세로가 2, 가로가 N이라면,

주어진 직사각형으로 세로 2를 만들 수 있는 최소 단위를 생각해 보자.

직사각형을 채운다고 했을 때, 마지막에 올 수 있는 경우를 생각해 보는 것이다.

2X1과 1X2를 사용하므로, 두 직사각형을 둘 다 사용해서 세로 2를 만들 수는 없다.

위의 그림과 같이 2가지밖에 존재하지 않는다.

D[N] : 세로길이 2, 가로길이 N일 때 2X1, 1X2 직사각형으로 채울 수 있는 경우의 수

1) D[N-2] 을 구하는 경우(N-2를 채우는 경우)와

2) D[N-1] 을 구하는 경우(N-1을 채우는 경우)가 존재한다.

이 두 가지를 D[N]으로 표현하면 

D[N] : D[N-2] + D[N-1] 이다.

for문 같은 것으로 순서대로 눈덩이 굴리듯 쌓아가는 것이 bottom-up 방식

재귀호출로 구현하게 되면 top-down 방식이라고 한다.

다이나믹 방식에서 중요한 건 다음에 같은 연산이 필요할 때 미리 계산해 둔 값을 이용하여 연산량을 줄이는 것이다.

저장을 위한 메모리가 더 필요하게 되지만, 속도가 빨라지는 것이다.

코드 보기