[다이나믹 프로그래밍] ▲ 문제3 - 바닥 공사(223p)

[이코테] 문제3 - 바닥 공사(223p)

(한줄평) 코드는 짧으나 점화식을 떠올리기가 쉽지 않았던 문제로 복습이 꼭 필요!!

풀이 시간: 30분 이내

 

1) 문제 해결 아이디어

가로 길이: n, 세로 길이: 2 인 직사각형 바닥을 1*2, 2*1, 2*2 3가지 타일로 채울 수 있는 경우의 수를 구하는 문제다. 이 문제 또한 다이나믹 프로그래밍의 기초 예제에서 빠질 수 없는 타일링 문제 유형이다.

 

왼쪽부터 타일을 채운다고 했을 때 아래와 같이 2가지 경우로 나눠볼 수 있다.

1. i - 1까지 이미 채워져있다면,

i번째를 채우기 위해 사용할 수 있는 타일은 (2 * 1) 1가지 경우다.

2. i - 2까지 이미 채워져있다면,

i - 1 ~ i 번째를 채우기 위해 사용할 수 있는 타일은

(1*2) 2개, (2*2) 1개 2가지 경우가 있다. 

Q. 여기서 (2*1) 2개를 채우는 경우를 제외하는 이유는?

(2*1) 2개를 채우는 경우는 1에서 경우의 수와 동일하므로 제외해야한다!!!

이것을 간과한다면 이 문제는 틀릴 수 밖에 없다~~~

2) 소스코드

n = int(input())  # 가로 길이

d = [0] * 1001    # 바닥을 채우는 경우의 수
d[1], d[2] = 1, 3 
for i in range(3, n + 1):
  # i - 1번째까지 다 채워진 경우 2*1 1개 1가지만 가능
  # i - 2번째까지 다 채워진 경우 1*2 2개/2*2 1개 2가지만 가능
  d[i] = (d[i - 1] + d[i - 2] * 2) % 796796

print(d[n])

 

[출처] https://www.youtube.com/watch?v=5Lu34WIx2Us&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=6