[Algorithm] DP - 백준 11727

오늘은 DP 문제 중 2xn 타일링 2편 문제를 풀어봅시다.

11727

결과 : 맞았습니다!!

풀이 시간 : 1시간 미만 성공

풀이 과정

2xn 타일링 1편 문제와 마찬가지로 패드를 이용하여 2x4 크기의 직사각형까지 그려서 규칙을 알아내고자 했습니다. 찾은 규칙은 다음과 같습니다.

1. 전 단계의 직사각형에 추가로 2x1 직사각형을 그립니다.
2. 두 단계 이전의 직사각형에 추가로 직사각형을 그립니다.
   1. 1x2 직사각형 2개
   2. 2x2 직사각형 1개

따라서 a[n] = a[n-1] + a[n-2] * 2입니다.

코드 비교

나의 코드 (PyPy3)

n = int(input())

memory = [0, 1, 3]

for i in range(3, n+1):
    memory.append(memory[i-2] * 2 + memory[i-1])

print(memory[n] % 10007)

랭킹 99위의 코드 (dbsdbxkrzz, PyPy3)

import sys
input = sys.stdin.readline


def recur(cur):
    if cur > n:
        return 0
    if cur == n:
        return 1
    if dp[cur] != -1:
        return dp[cur]
    dp[cur] =(recur(cur + 1) + recur(cur + 2) * 2) % 10007
    return dp[cur]

n = int(input())
dp= [-1] * n
print(recur(0))

로직은 같지만 랭킹 99위님은 반복문이 아닌 재귀함수를 사용하셨습니다. 또한, 매 값마다 나머지 계산을 해서 속도를 향상시키셨습니다.

느낀점

2xn 타일링 1편 문제와 같이 규칙 찾기 능력을 향상시킨 문제였습니다. 문제에 따라서 반복문을 쓸지 재귀함수를 쓸지도 고민해야겠습니다. 앞으로도 많은 DP 문제 올리겠습니다. 감사합니다!