[DP] boj 11726, 11727 - 2xn 타일링

+ 연결 문제 2133

백준 11726, 11727은 점화식으로 해결할 수 있다. 현재 값과 이전 값들이 어떤 관계를 갖는지 찾는 게 점화식인데, 이 개념을 단순한 숫자 간의 계산보다 그림으로 이해하게 해주는 문제들이다.

너비 i를 채울 수 있는 경우의 수는 직전의 너비 i-1에서 가장 오른쪽에 생긴 빈칸 1x2를 채우는 경우의 수 + 너비 i-2에서 가장 오른쪽에 비워둔 빈칸 2x2를 채우는 경우의 수의 합이다.

 

for문을 도는 대신 재귀 함수를 선언하고 이전에 계산한 값을 보존하는 방법을 찾았다. 이를 이용하는 게 더 빠르다. 메모리 차이는 아직 모르지만...

11726

방법 1

import sys

n = int(sys.stdin.readline())
dp = {1:1, 2:2}

for i in range(3, n+1):
    dp[i] = dp[i-1] + dp[i-2]

print(dp[n] % 10007)

방법 2

재귀 + 파이썬 함수의 동작 방식을 활용. __cache 변수를 함수 정의부에 선언했다. 이와 같이 함수 정의부에 쓴 건 함수 호출, 종료와 상관 없이 함수 자체가 메모리에서 지워지기 전까지는 값이 유지된다. 참고 링크에서 DP 방식 중 마지막 부분이다.

import sys

def calcNumberOfCases(num, __cache = {1:1, 2:2}):
    if num in __cache:
        return __cache[num]

    __cache[num] = calcNumberOfCases(num-2) + calcNumberOfCases(num-1)
    return __cache[num]

n = int(sys.stdin.readline())
print(calcNumberOfCases(n) % 10007)

---

11727

방법 1

11716의 방법 2와 같다.

import sys

def calcNumberOfCases(num, __cache = {1:1, 2:3}):
    if num in __cache:
        return __cache[num]
    __cache[num] = 2 * calcNumberOfCases(num-2) + calcNumberOfCases(num-1)
    return __cache[num]

n = int(sys.stdin.readline())
print(calcNumberOfCases(n) % 10007)

방법 2

예전에 푼 방식인데 점화식 접근을 다르게 했다. 신기하게...

import sys

def tile(N, __cache = {1:1, 2:3}):
    if N in __cache:
        return __cache[N]
    if N % 2 == 0:
        temp = 1
    else:
        temp = -1

    __cache[N] = 2 * tile(N-1) + temp # N이 짝수면 +1, 홀수면 -1
    return __cache[N]

n = int(sys.stdin.readline())
print(tile(n) % 10007)