[이.취.코] Chap 8. 다이나믹 프로그래밍 - 바닥 공사

1. 바닥 공사

• 난이도
  • 중하
• 풀이 시간
  • 20분
• 시간 제한
  • 1초
• 메모리 제한
  • 128MB

A. 문제

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

이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하라.

a. 예를 들면.

2x3 크기의 바닥을 채우는 경우의 수는 5가지이다.

b. 입력 조건

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

c. 출력 조건

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

d. 테스트 케이스

• 입력 예시

  
  3
  
  

• 출력 예시

  
  5
  
  

B. 내 답안

n = int(input())  
  
tale = [(2,2),  
 (1,2),  
 (2,1)]  
  
array = []  
m = n // 2 + n % 2  
for i in range(m):  
    one = [0] * m  
    if i < n-1:  
        one[i] = 4  
    for j in range(len(one)):  
        if one[j] == 0:  
            one[j] = 1  
  
    array.append(one)  
  
print(array)  
  
# 실패 / 48분

a. 회고

풀이

반성

• 점화식으로 접근하는 방법에 대해 생각하지 못했다.
  • 점화식을 완전히 이해하지 못했다.

결론

• 마지막 부분의 반복성과 1항, 2항을 얻을 수 있는지를 확인하자.
• DP 문제를 많이 풀어봐야한다.

C. 문제 해설

다이나믹 프로그래밍 문제에서는 종종 결과를 어떤 수로 나눈 결과를 출력하라고 한다. 이는 단지 결괏값이 굉장히 커질 수 있기 때문에 그런 것이다.

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

1. 왼쪽부터 i-1까지 길이가 덮개로 이미 채워져 있으면 2x1의 덮개를 채우는 하나의 경우밖에 없다.

   

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

   

왼쪽부터 i-2 미만의 길이에 대해서는 고려할 필요가 없다. 사용할 수 있는 덮개의 형태가 최대 2x2의 직사각형 형태이기 때문이다. 따라서 바닥을 채울 수 있는 형태는 위의 경우밖에 없다.

왼쪽부터 i-2까지 길이가 덮개로 이미 채워져 있는 경우 덮개를 채우는 방법은 2가지 경우가 있다. 이 두 방법은 서로 다른 것이므로, 결과적으로 a_{i}는 a_{i-1} + a_{i-2} + a_{i-2}가 된다.

a. 책 답안

python-for-coding-test/7.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #문제 #풀이 #다이나믹프로그래밍 #바닥공사