반응형
https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
문제이해
입력받은 n만큼 세로 2 가로 n길이의 직사각형에 1x2 혹은 2x1 타일로 채우는 방법의 수를 구하면 된다. n의 입력값이 1000이기에 O(n^2)로 풀어도 되겠다는 생각은 들었다.
접근법
완전탐색을 사용하려 보니 재귀함수를 사용해야할거 같다는 생각으로 이어졌다. 하지만 파이썬에서는 기본적으로 재귀함수의 깊이 제한이 걸려있기 때문에 dp를 사용해야한다. 그래서 dp방법으로 풀이를 해보고자 했다.
코드
import sys
n = int(sys.stdin.readline().strip())
memo = {1:1, 2:2}
def countBlock(n:int) -> int :
for i in range(3, n + 1) :
if i not in memo :
memo[i] = memo[i - 1] + memo[i - 2]
return memo[n]
print(countBlock(n)%10007)
반응형
'알고리즘' 카테고리의 다른 글
백준 1181 단어정렬 파이썬 풀이 (3) | 2024.02.07 |
---|---|
백준 1003 피보나치 함수 파이썬 풀이 (0) | 2024.02.07 |
백준 1676 팩토리얼 0의 개수 파이썬 풀이 - recursionError (0) | 2024.01.19 |
백준 10992 별 찍기 - 17 파이썬 풀이 (2) | 2024.01.18 |
백준 10991 별 찍기 - 16 파이썬 풀이 (0) | 2024.01.18 |