Python 85 - 다이나믹 프로그래밍 실전문제3 ("바닥 공사")

난이도 ●◐○    l    풀이 시간 20분    l    시간 제한 1초    l    메모리 제한 128MB    l

문제 

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 x 2의 덮개, 2 x 1의 덮개, 2 x 2의 덮개를 이용해 채우고자 한다.

이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2 x 3 크기의 바닥을 채우는 경우의 수는 5가지이다.

입력조건

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

출력조건

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

문제해설

이 문제 또한 마찬가지로 다아나믹 프로그래밍의 기초예제에서 빠질 수 없는 타일링 문제 유형이다. 다아나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라는 내용이 들어가 있는 경우가 많다. 이 문제에서도 796,796으로 나눈 나머지를 출력하라고 하는데, 이는 단지 결과값이 굉장히 커질 수 있기 때문에 그런 것이다. 따라서 값을 계산할 때마다 특정한 수로 나눈 나머지만 취하도록 하면 된다.이 문제 또한 그림으로 그려서 생각하면 어렵지 않게 풀 수 있다. 예를 들어 N이 3일 때 바닥을 덮개로 채울 수 있는 모든 경우의 수는 다음과 같다.

또한 왼쪽부터 차례대로 바닥을 덮개로 채운다고 생각하면 어렵지 않게 점화식을 세울 수 있다.

또한 이문제 역시 i번째 위치에 대한 최적의 해를 구할 떄 왼쪽부터(i -3)번째 이하의 위치에 대한 최적의 해에 대해서는 고려할 필요가 없다. 왜냐하면 사용할 수 있는 덮개의 형태가 최대 2 x 2크기의 직사각형 형태이기 떄문이다. 다시 말해 바닥을 채울 수 있는 형태는 위에서 언급한 경우밖에 없다. 따라서 다음과 같이 점화식을 세울 수 있다.

왼쪽부터 N - 2 까지 길이가 덮개로 이미 채워져 있는 경우 덮개를 채우는 방법은 2가지 경우가 있다. 이 두 방법은 서로 다른 것이므로,

답안예시

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

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

# 다이나믹 프로그래밍(Dynamic Programming) 진행 (보텀업)
d[1] = 1
d[3] = 3
for i in range(3, n + 1):
	d[i] = (d[i - 1] + 2 * d[i - 2] % 796796
    
# 계산된 결과 출력
print(d[n])

 

 

 

 

 

 

 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding