문제설명

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 이 얇은 바닥을 1x2, 2x1, 2x2 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.

접근

1x2, 2x1, 2x2 덮개
왼쪽부터 바닥을 채워나간다고 가정하면, 마지막 덮개는 가로길이가 1이나 2일 것이다.

• 마지막 덮개의 가로길이가 1인 경우
• 마지막 덮개의 가로길이가 2인 경우

점화식
a_i = a_i-1 + a_i-2 x 2

마지막 덮개의 가로길이가 1인 경우는 2x1 덮개로 마무리 짓는 경우이고, 나머지 한 경우는 2x2 덮개로 마무리 짓거나 1x2 덮개 두개를 가로로 이어붙여 마무리 짓는 두 가지 경우로 생각할 수 있다. 결과 저장용 리스트에 저장된 값은 바닥의 특정 가로 길이를 채우는 경우의 수이다. 따라서 그 다이나믹 프로그래밍의 보텀업 방식으로 문제를 해결할 수 있다.

풀이

n = int(input())

// 결과 저장용 리스트
d = [0] * 1001

// 가로길이가 1인 경우와 2인 경우의 바닥을 채우는 경우의 수
d[1] = 1
d[2] = 3
for i in range(3, n+1):
	d[i] (d[i-1] + 2 * d[i-2]) % 796796
    
print(d[n])

배운점

특정 크기의 몇가지의 덮개(타일)로 크기가 일정한 공간을 채우는 문제는 다이나믹 프로그래밍으로 접근할 수 있다.