[이코테] 바닥공사

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

 

 

 

이 때 바닥을 채우는 모든 경우의 수를 구하시오.

 

입력 조건

N이 주어진다. (예시 3)

출력 조건

해당 경우의 수를 796796 으로 나눈 나머지를 출력한다 (예시 5)

 

문제풀이

이 문제를 처음 봤을때 이상하게 생각한게, 가로 타일이 2개가 깔렸을 때 그걸 2가지 경우의 수로 보느냐, 1개로 보느냐였다. 그것때문에 첨에 틀렸는데.. 답안을 보니 모양만 같으면 한가지 경우의 수로 보게 되어있었다.

 

이건 점화식을 이런 논리로 짤 수 있는데...

구하고자 하는 경우의 수 = (1칸이 모자란 경우의 수 * 남은 1칸 채우는 경우) + (2칸이 모자란 경우의 수 * 남은 2칸 채우는 경우)

이 때, 남은 2칸을 채우는 경우의 수가 원래는 세로 2개, 가로 2개, 정사각형 하나 이렇게 3 개로 볼 수 있으나.

이 중에 세로 2개를 쓰는 것은 1칸이 모자란 경우의 수와 겹치기 때문에 결국 2 개로 볼 수 있다.

 

dp[1] = 1 # 세로 하나

dp[2] = 3 # 세로 두개, 가로 두개, 정사각형 하나

dp[i] = (dp[i - 1] * 1) + (dp[i - 2] * 2) # 하나가 모자란걸 채울 때 + 두개가 모자란걸 채울 때

 

N = int(input())
dp = [0 for _ in range(0,N+1)]
# 이 문제는 꽃히는 타일 순서가 다른것 까지 포함하지 않고 단순 모양만 봄
for i in range(1,N+1):
    if i == 1:
        dp[i] = 1
    elif i == 2:
        dp[i] = 3
    else:
        dp[i] = dp[i - 1] + 2 * (dp[i - 2])
print(dp,dp[N] % 796796)