★파이썬(Python) 코테 대비 DP : 백준 11727번 2xn 타일링 2

[시작 체크 리스트]

1. 1시간 지났으나 발상 불가 또는 아예 다른 길
2. 코드 50% 정도 완성
3. 1시간 보다 더 걸려서 코드 완성
4. 코드는 다 돌아가는데 효율성에서 걸림
5. 코드 완성

[잘못 발상한 코드]

1. 발상

노가다를 해보니, 1일 때 1개, 2일때 3개, 3일때 5개, 4일때 11개, 5일때 21개, 6일때 43개인거 발견하고 dp=[1,3,5] 리스트를 만든 후, dp[n]=dp[n-1]*2 라고 생각했는데, 애초에 그러면 5번째가 안맞음. 한마디로 처음부터 계산 틀려서 틀린 엉망진창 발상

2. 코드

n=int(input())
dp=[1,3,5]
if(n>3):
    for i in range(3,n):
        dp.append(dp[i-1]*2+1)
print(dp[n-1])

[완료 후 체크 리스트]

1. 아예 모르겠음
2. 중간 정도 이해함
3. 완벽히 이해함

[첨언]

근데 아직도 왜 타일링 해줄 때 전 타일 맨 뒤에 덧붙여주는 경우만 생각하면서 세어주면 겹치는 경우 없이 완벽히 세어지는 이유를 이해하지는 못함. 그냥 그런가보다~의 느낌임. 이건 시간이 지나서 언젠가 다시 생각해보기로 하자.

[구글링 이후]

1. 발상

n번째의 타일링을 하는 방법에는
1. n-1 번째에 1 * 2 타일링을 해주기
2. n-2 번째에 2 * 1 타일링 2번 해주기
3. n-2 번째에 2 * 2 타일링 1번 해주기

이 때, n-2인 경우가 2개이므로, 점화식은 dp[n]=dp[n-1]+dp[n-2]*2

2. 코드

n=int(input())
dp=[1,3,5]
if(n>3):
    for i in range(3,n):
        dp.append(dp[i-1]*2+1)
print(dp[n-1])

(출처 : https://www.acmicpc.net/problem/11727)