#Algorithm
문제 번호
11726 2xn 타일링(S3)
알고리즘 + 이론
DP
정답 코드
# 11726번
# 1 <= n <= 1000
# n = 1 일때 1개
# 2 일때 2개
# 3 일때 3개
# 4 일때 5개
# 5 일때 8개
# 6 일때 13개
# 7 일때 21개
# 8 일때 34개
# 9 일때 55개
# r[n] = r[n-1] + r[n-2]
n = int(input())
n -= 1
r = [0 for _ in range(1000)]
r[0] = 1
r[1] = 2
if n > 1:
for i in range(2,n+1):
r[i] = r[i-1] + r[i-2]
print(r[n]%10007)
느낀점 & 피드백
점화식을 구하니 바로 풀렷다. 이거 점화식을 나중에 못 구하거나 DP가 아닌데 DP로 접근했을 때 경우를 연습해봐야할 것 같다.
이 글이 도움이 되셨나요?