다이나믹 프로그래밍 (Dynamic Programming) (4) - 실전문제 8.4) 바닥 공사

문제)

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 바닥을 타일로 모두 채워야 한다. 이 때 타일의 종류는 3가지 존재한다.

• 1 x 2 직사각형 타일
• 2 x 1 직사각형 타일
• 2 x 2 정사각형 타일

이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.

입력조건)

• 첫째 줄에 N이 주어진다. (1 <= N <= 1,000)

출력조건)

• 첫째 줄에 2 x N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

입력예시)

3

출력예시)

5

---

풀이)

이 문제도 역시 다이나믹 프로그래밍의 바텀업 방식을 사용해서 간단히 해결할 수 있다. 핵심 아이디어는 다음과 같다.

반복문을 N까지 돌면서 현재 가로 길이일 때 가능한 가짓수를 결과 리스트에 저장할 것이다. 반복문의 현재 인덱스를 i라고 하자. 이 때 두 가지 경우가 발생하게 된다.

1. i-1까지 모두 타일이 채워져 있는 경우 => 가로로 한칸만 채우면 된다. => 2 x 1 타일로 덮는 경우 1가지
2. i-2까지 타일이 채워져 있는 경우 => 가로로 두칸을 채우면 된다. => 1 x 2 타일로 덮는 경우 + 2 x 2 타일로 덮는 경우, 즉 2가지

따라서 결과 리스트의 현재 인덱스 i 에는 결과 리스트[i-1] + 결과 리스트[i-2] * 2 를 저장하고 결과 리스트의 N번째 인덱스에 해당하는 값을 출력하면 원하는 출력 결과를 얻을 수 있을 것이다.