[백준-파이썬] 11726번: 2Xn 타일링

백준 문제 보러 가기~!

코드😎

n = int(input())
dy = [0]*(n+1)


if n == 3:
    print(n)

else:
    dy[1] = 1
    dy[2] = 2

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

    print(dy[n]%10007)

설명😊

다이나믹 프로그래밍!!

일단 n이 1이라면, 당연히 답은 1이다. 세로로만 세울 수 있다.
n이 2라면 답은 2이다. 세로로 두개 혹은, 가로로 두개가 가능하다.

n이 3이라면 두 가지 경우로 나눌 수 있다.
맨 끝 부분에서, 세로로 하나인 경우, 그러면 그 안쪽부분은 2개가 있다. 그럴 때 안쪽 2개를 배치하는 방법은 n=2일 때 경우의 수와 같다.
맨 끝 부분에서 가로로 두개를 둘 경우, 안쪽에는 하나만 남았다. 그러면 안쪽에 하나 배치하는 방법은 n=1일 때의 경우의 수와 같다.
이 두 가지 경우를 더하면 답이다.

n=4일 때도, 똑같이 두 가지 경우로 나눠서 풀 수 있다.
맨 끝 부분이 세로로 하나인 경우, 안쪽 3개를 배치하는 방법은 n=3일 때 답과 같다.
맨 끝 부분이 가로로 두개를 둘 경우, 안쪽은 2개가 남았다. 안쪽 2개를 배치하는 방법은 n=2일 때 답과 같다.
이 두 가지 경우를 더하면 n=4일 때 답이다..

점화식..^^처럼 세워보면
타일이 n개일 때 답은 n-1일 때의 답과 n-2일 때의 답을 더한 것이다.

헷갈렸던 부분 😂

n==1인 경우를 생각하는 게 어려웠다. 처음에는 if n==3 부분은 없고 else 부분만 있었다.
인덱스 에러가 나와서, 왜 그렇지? 고민하다가 n=1을 넣어보니까 에러가 나는 것을 보고 알았다.

만약에 n=1이라면, dy의 길이가 2이다.(인덱스로 접근하려고 하면 0, 1로만 가능) 그런데 dy[2]에 대입하려고 하니까, 인덱스 에러가 뜬다.