n = int(input())
d = [0] * 1001
d[1] = 1
d[2] = 3
for i in range(3, n + 1):
d[i] = (d[i - 1] + d[i - 2] * 2) % 796796
print(d[n])
Code Review
이번 문재는 2 X N 인 직사각형이 있을 때 1 X 2, 2 X 1, 2 X 2 덮개를 이용해 채울 수 있는 경우의 수를 구해보는 것이었습니다. 점화식을 떠올리기 쉽지 않은 문제였습니다. 따라서 그림을 이용하여 경우의 수를 어떻게 구할 수 있을지 생각해보았습니다. 먼저 덮개를 왼쪽부터 채운다고 가정하고 만약 i - 1 번째 까지 타일을 모두 채웠을 때,
2 X 1 덮개로 나머지 부분을 채우는 방법 1가지만 존재합니다. 만약 i - 2 번째 까지 타일을 모두 채웠을 때,
2 X 2, 그리고 1 X 2 덮개 두개로 채우는 방법 2가지가 존재합니다. 2 X 1 덮개 두개로 채우는 방법도 존재하지만 그것은 이미 첫 번째에서 고려해주었으므로 제외합니다. 이렇게 그림으로 표현하면 점화식을 쉽게 떠올릴 수 있습니다. 아래 점화식은 그림으로 구한 것을 식으로 표현해준 것 입니다. -a(i) = a(i-1) + a(i-2) * 2 따라서 이렇게 구한 점화식을 이용해 코드를 구현해주었습니다. 현재까지 계산한 결과를 저장시킬 별도의 리스트 d 를 만들어주고 i-1, i-2 번째를 고려하여 현재 값을 계산할 것이므로 d[1], d[2] 의 값을 구해주고 반복문은 3부터 실행되도록 해주었습니다. 구한 점화식을 이용해 d[i] 값을 계산하도록 해주었고 최종 d[n] 값을 출력하면 경우의 수를 출력할 수 있습니다.
댓글