오늘은 DP 문제 중 2xn 타일링 1편 문제를 풀어봅시다.
11726
문제 : https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
결과 : 맞았습니다!!
풀이 시간 : 1시간 미만 성공
풀이 과정
패드를 이용하여 2x4 크기의 직사각형까지 그려서 규칙을 알아내고자 했습니다. 전 단계의 직사각형에 추가로 2x1 직사각형을 그리고, 두 단계 이전의 직사각형에 추가로 1x2 직사각형 2개를 그리면 되는 규칙이 나오게 되었습니다. 따라서 a[n] = a[n-2] + a[n-1]입니다.
코드 비교
나의 코드 (PyPy3)
n = int(input())
memory = [0, 1, 2]
for i in range(3, n+1):
memory.append(memory[i-2] + memory[i-1])
print(memory[n] % 10007)
랭킹 99위의 코드 (dbsdbxkrzz, PyPy3)
import sys
input = sys.stdin.readline
dp = [0] * 1001
dp[1] = 1
dp[2] = 2
for i in range(3, 1001):
dp[i] = (dp[i - 1] + dp[i - 2]) % 10007
print(dp[int(input())])
로직은 같지만 랭킹 99위님은 결과값을 리스트에 저장할 때마다 나머지 계산을 해서 속도를 향상시키셨습니다.
느낀점
처음 문제를 볼 때는 규칙이 안 보여서 굉장히 막막했는데, 패드에 그리면서 하니 도형이 한 눈에 들어와서 규칙을 찾을 수 있었습니다. 앞으로 도형 문제나 수 규칙 문제가 나오면 패드나 메모장에 기록하면서 풀어야겠습니다. 많은 DP 문제를 풀면서 규칙을 발견하는 안목또한 길러야겠습니다.
오늘의 글은 여기까지입니다. 감사합니다!
'Algorithm' 카테고리의 다른 글
[Algorithm] DP - 백준 11727 (0) | 2023.11.19 |
---|---|
[Algorithm] DP - 백준 1463 (0) | 2023.11.07 |