[DP] 이코테 “바닥 공사” Python 풀이

문제

• 가로의 길이가 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

풀이

• 왼쪽부터 i-1 까지의 길이가 이미 덮개로 채워져 있으면, i 번째를 채우는 방법은 2 x 1 의 덮개를 채우는 하나의 경우밖에 없습니다.
• 왼쪽부터 i-2 까지의 길이가 이미 덮개로 채워져 있으면, i-1 번째와 i 번째를 채우는 방법은 1 x 2 덮개 2개를 넣는 경우, 혹은 2 x 2 의 덮개 하나를 넣는 경우로, 2가지 경우가 존재합니다.
• 따라서, [ a(i) = a(i-1) + a(i-2) + a(i-2) ]가 됩니다.
  • 즉,[ a(i) = a(i-1) + a(i-2) x 2 ]가 됩니다.

예제 코드

# 정수 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])

참고

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