이코테-chapter8: 바닥 공사

정리 내용

문제 설명

• 난이도: 중
• 시간 제한: 1초
• 메모리 제한: 128mb
• 가로의 길이가 n, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.
• 이 얇은 바닥을 12 덮개, 21 덮개, 2*2 덮개를 이용해 채우려고 한다.
• 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하라.
• 첫째 줄에 n이 주어진다.
• 첫째 줄에 2 * n 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

문제 풀이

• 위 문제 같은 타일링 문제는 다이나믹 프로그래밍 단골 문제이다.
• 다이나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라는 내용이 들어가 있는 경우가 많다.
• 이유는 단지 결과값이 매우 커질 수 있기 때문이다.
• 왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 어렵지 않게 점화식을 세울 수 있다.
  1) 왼쪽부터 i-1까지 길이가 덮개로 이미 채워져 있으면 21의 덮개를 채우는 하나의 경우밖에 존재하지 않는다.
  2) 왼쪽부터 i-2까지 길이가 덮개로 이미 채워져 있으면 12 덮개 2개를 넣는 경우, 2*2의 덮개 하나를 넣는 경우로 2가지 경우가 존재한다.
• 이 문제의 점화식은 아래와 같다.
• a(i) = a(i-1) + a(i-2) * 2

소스 코드

n = int(input())

d = [0] * 1001

# 다이나믹 프로그래밍 진행 bottom-up
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])

출처 & 깃허브

이것이 취업을 위한 코딩 테스트다 with python

github