[CodingTest] 바닥공사 ( dp )

 

◎ 문제

• 가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다.
• 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다.
• 이 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오.
• 예를 들어, 2X3 크기의 바닥을 채우는 경우의 수는 5가지이다.

 

 

- 입력 조건

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

 

- 출력 조건

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

 

- 입력 예시

3

- 출력 예시

5

 

 

◎ 문제풀이

 

작은 타일로 큰 영역을 채우는 문제이다. 부분으로 목표를 만드는 문제이므로 DP를 연상할 수 있다. 영역은 NX2로 세로는 고정되어 있고 가로길이가 동적으로 변한다. 그러므로 경우의수는 가로길이에 따라 달라진다. 

 

작은 타일의 가로길이의 경우는 1과 2이다. 

 

1) 가로길이가 1인 경우는 한 가지이다.

 

 

2) 가로길이가 2인 경우는  세 가지이다.

 

 

여기서 중요한 개념은 1) 과 2)를 독립사건으로 만드는 것이다. 타일의 가로길이가 2이면 반으로 깨뜨리지 않는 이상 가로길이가 1이 될 수 없다. 타일의 가로길이가 1이면 두 개로 붙여야 2가 될 수 있다.  그런데 2x1을 두 개 붙이면 가로길이가 2가 된다. 그러면 독립사건이 되지 않는다. 그래서 2x1을 두 개 붙여 가로길이가 2가 되는 경우는 제외한다.  제외되는 이유는 뒤에서 더 설명하겠다. 

 

이렇게 가로길이가 2인 경우는 두 가지가 된다.

 

 

 

이제 1)과 2)는 독립사건이 되었다. 그러므로 큰 영역을 채우는 경우의 수는 크게 두가지 경우로 분류된다.

 

 

 

2x1을 두개 붙여 가로가 2가 되는 경우는 첫번째 경우에 이미 포함된다. 

 

(N-1)X2 타일에서 나올수 있는 경우의 수를 An-1 라고 하자. 첫번째 경우는 하나 밖에 없다.  (N-2)X2 타일에서 나올 수 있는 경우의 수를 An-2라고 하자. 두 번째는 끝에 두 종류( 2x2 , 1x2 )의 타일이 올수 있다. 그러므로 두번째 경우에서 나올 수 있는 총 경우의 수는 2 x An-1이다.

 

첫번째와 두번째는 서로 독립사건이므로 경우의수는 더하기 연산으로 구한다. 

 

An = An-1 + 2xAn-2

 

점화식이 도출되었으니 DP의 Bottom-Up 방식으로 An을 구하면 된다. 

 

 

◎ 코드

n = int(input())
d = [0]*(n+1)

d[1] = 1
d[2] = 3

for i in range(3,n+1) :
  d[i] = d[i-1] + d[i-2]*2 #점화식
  
print(d[n]%796796)

 

 

---

 

 

참고자료

이것이 취업을 위한 코딩 테스트다 with 파이썬 : 네이버 도서