문제
문제 : https://www.acmicpc.net/problem/11727
양의 정수 n을 입력받아 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 구하여라.
+ 이번 글도 다른 사람 풀이를 참고한다.
점화식
n = 1일 때부터 시작해 결과를 그려보면 아래 그림과 같다.
조금 더 그려보면 아래와 같은 패턴이 반복되는 것을 확인할 수 있다.
즉, 확인한 패턴을 점화식으로 표현하면 다음과 같다.
$$ counts(n) = counts(n - 1) + 2counts(n - 2) $$
이전 값 하나만 참조할 뿐 아니라, 여러 값을 참조하는 경우도 충분히 있을 수 있다……. 생각해보면 피보나치 함수도 그렇다.
구현
이전에 계산한 값을 반복적으로 확인해야 하므로 메모이제이션을 활용한다.
1. 테이블에 초기값을 설정한다.
memo = [0, 1, 3]
2. 반복문으로 테이블 인덱스가 n이 될 때까지 값을 추가한다.
점화식을 만족하도록 계산하되 테이블에 추가할 때 10007로 나눈 나머지를 추가한다.
for i in range(3, int(n) + 1):
memo.append((memo[i - 1] + 2 * memo[i - 2]) % 10007)
3. 테이블 인덱스가 n에 해당하는 값이 결과값이 된다.
전체 소스는 다음과 같다.
def solution(n):
memo = [0, 1, 3]
for i in range(3, int(n) + 1):
memo.append((memo[i - 1] + 2 * memo[i - 2]) % 10007)
return memo[n]
n = int(input())
print(solution(n))
참고 문서
https://girawhale.tistory.com/34
https://jamesu.dev/posts/2020/01/14/baekjoon-problem-solving-11727/