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

N을 입력 받았을 떄  가로가 N 세로가 2인 바닥이 생긴다.

그떄 1 x2, 2x1, 2x2 크기의 3종류의 타일로 덮을수  있는 경우의 수를 찾아라.

 

 

나의 코드

n=int(input())

dp=[0]*(n+1)
dp[1]=1
dp[2]=3
for i in range(3,n+1):
    dp[i]=dp[i-1]*2-1

print(dp[n]%796796)

음.. 이번 DP 문제도 확신이 안든다... 애초에 위 코드는 결국 다이나믹프로그래밍이 아니라 그냥 입력값*2-1을 출력한 값이기도 하고...

확실한 근거를 바탕으로 패턴을 찾아야 하는데 그 확실한 근거는 늘 안보이고 짜잘한 의심? 정도를 가지고 코드를 짜게 된다..
 나의 그 짜잘한 의심은 아래 사진과 같다. 보라색 선으로 표시한 부분을 보면 i번쨰의 경우의 수는 i-1번째의 경우의 수를 포함 하되 양옆으로 1칸을 공유한채 대칭되어 나타난다는 것이다. 또한 1가지가 중복이 되어 -1을 해준다 !

 

 

 

 

정답코드

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

또 기본 접근 자체를 이상하게 했다..

이전 값들을 토대로 다음 값을 유추 해서 점화식을 세운다 ! 라는 기본 전체를 자꾸 헤이하게 대충 풀려고 해서 그런것 같다..

 

 

 

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

 

 

 

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

2)에서 그렇다면 아래 와 같이 2x1 타일 2개를 붙이는 경우는 안되는가?

그렇다 안된다.  왜냐하면 i-1번의 문제에 이미 포함을 했기 때문이다 !

 

 

 

어우 다이나믹 아직 체화가 덜되서 어렵다.....
제발 !!!!  "이전 값들을 토대로 다음 값을 유추해서 점화식을 세운다 !!"  유념하기 !!