[이것이 코딩테스트다] 다이나믹 프로그래밍 - 바닥공사 문제풀이

문제

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 이 얇은 바닥을 덮개로 채우고자 하는데, 해울 수 있는 모든 경우의수를 구하라. 덮개는 1 X 2, 2 X 1, 2 X 2 이렇게 3가지로 구성되어있다.

 

만약 N이 3일 경우

1) (2 X 1) + (2 X 2)

2) (2 X 2) + (2 X 1)

3) (1 X 1) + (1 X 1) + (1 X 1)

4) (2 X 1) + (1 X 2) + (1 X 2)

5) (1 X 2) + (1 X 2)  + (2 X 1)

 

총 5가지 경우가 나온다.

 

 

 

 

정답코드

# 정수 N을 입력 받기
n = int(input())

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 1001

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
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])

출처 : github.com/ndb796/python-for-coding-test/blob/master/8/7.py

 

 

 

 

문제풀이

해당 문제는 점화식을 세워서 풀어야하는 문제이다.

 

첫번째 경우.

왼쪽부터 i - 1까지 길이가 덮개로 이미 채워져있으면 2 X 1 덮개를 채우는 하나의 경우만 존재한다.

가로길이: i - 1

2 X 1

 

두번째 경우.

왼쪽부터 i -2까지 길이가 덮개로 이미 채워져있으면 1 X 2 덮개 2개를 넣는 경우, 혹은 2 X 2 덮개 하나를 넣는 경우로 2가지 경우가 존재한다.

 

가로길이: i - 2

1 X 2 (2개) 또는 2 X 2 (1개)

사용할 수 있는 덮개의 최대 길이는 2 X 2이므로 N - 2 미만의 길이는 생각할 필요가 없다.

위 경우의수를 정리하여 점화식을 세우면 아래와 같다.

 

a의 i = a의 i-1 + (a의 i-2 X 2)

 

i-1까지 채워져있을 경우 덮개를 채우는 경우는 무조건 1개이고, i-2까지 채워져있을 경우 덮개를 채우는 경우는 2개이기 때문에 뒤의 i-2에는 2를 곱해준다. 

 

for i in range(3, n + 1):
    d[i] = (d[i - 1] + 2 * d[i - 2])

 

위 점화식을 고려한 코드가 바로 이 코드이다. 각 dp 테이블의 위치에는 각 N일 경우에 채울 수 있는 경우의수가 설정되어있다.