해당 문제는 여기에서 확인하실 수 있습니다.
문제를 해결하기 위해 가로 길이가 n인 바닥을 채우는 방법의 수를 구하기 위해, 타일을 배치할 수 있는 두 가지 경우를 고려합니다. 첫 번째는 타일을 세로로 배치하는 경우이고, 두 번째는 타일을 가로로 배치하는 경우입니다. 이 두 가지 경우의 수를 합산하면 n을 채우는 모든 경우의 수를 계산할 수 있습니다.
이를 점화식으로 표현하면 다음과 같습니다: dp[n] = dp[n-1] + dp[n-2]. 여기서 dp[n-1]은 마지막 타일을 세로로 배치한 경우의 수를 나타내며, dp[n-2]는 마지막 타일을 가로로 두 개 배치한 경우의 수를 나타냅니다. 초기 조건으로는 dp[1] = 1과 dp[2] = 2를 설정합니다. 여기서 dp[1]은 가로 길이가 1일 때의 경우의 수이고, dp[2]는 가로 길이가 2일 때의 경우의 수를 나타냅니다.
가로 길이 n이 최대 60,000까지 주어질 수 있으므로 효율적인 계산이 필요합니다. 점화식을 기반으로 배열에 결과를 저장하며 반복적으로 계산하면 중복 계산을 방지할 수 있습니다. 또한, 경우의 수가 매우 커질 수 있으므로 계산 중간에 1,000,000,007로 나눈 나머지를 저장하여 결과값이 커지는 것을 방지합니다.
먼저 dp[1]과 dp[2]를 초기화한 후, dp[3]부터 dp[n]까지 점화식을 반복적으로 적용하여 값을 계산합니다. 최종적으로 배열의 dp[n] 값을 반환하면 n을 채우는 모든 경우의 수를 구할 수 있습니다.
def solution(n):
MOD = 1000000007
answer = [0] * (n + 1)
# 초기 조건: n이 1일 때 경우의 수는 1
answer[1] = 1
# 초기 조건: n이 2일 때 경우의 수는 2
if n > 1:
answer[2] = 2
# 점화식을 이용하여 경우의 수 계산
for i in range(3, n + 1):
answer[i] = (answer[i - 1] + answer[i - 2]) % MOD
# n번째 경우의 수 반환
return answer[n]