[이코테] 다이나믹프로그래밍 - 바닥 공사

해당 포스팅의 문제의 출처는 나동빈님의 이것이 취업을 위한 코딩 테스트 교재를 공부하면서 풀이할 때 본인의 사고 과정 흐름과 문제 풀이를 기록하기 위함 입니다. 

 

---

문제설명

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의 덮개를 이용해 채우고자 한다. 이 때 바닥을 채우는 모든 경우의 수를 구하여라.

입력조건

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

출력조건

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

사고과정

• DP풀 때, 왼쪽으로 부터 차례차례 하나씩 해나간다고 생각하고 도식화한 다음, N번째 기준으로 몇 번째 직전까지는 고려하지 않아도 되는지 관점으로 풀어보자.
• 점화식 세우는게 아직 익숙치 않고 어렵다..

풀이

import sys

N = int(input())
d = [0] * 1001

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])

 

위 부분에서 DP 테이블에 저장할 때, 애초에 796,696을 나눈 나머지 값으로 저장을 하는데, 처음엔 이에 대해 왜 이렇게 하는지 의심이 들었다. 그래서 해당 교재 깃헙 이슈에 가보니 이러한 궁금증 질문이 있었고 답변을 보니 나머지 연산 %의 분배법칙에 대해 새롭게 알게 되었다.