코테/프로그래머스
프로그래머스 level3 [ 2 x n 타일링] 파이썬
동 캄
2022. 4. 8. 20:47
반응형
https://programmers.co.kr/learn/courses/30/lessons/12900
코딩테스트 연습 - 2 x n 타일링
가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는
programmers.co.kr
https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
# 프로그래머스 2 x n 타일링
def solution(n):
answer = 0
dp = [0]*(n+1)
dp[0] = 1
dp[1] = 1
for i in range(2, n+1):
dp[i] = (dp[i-1]+dp[i-2])%1000000007
answer = dp[n]
return answer
위의 문제는 피보나치 수열을 이용한 dp 문제이다.
i번째의 경우의 수 = i-2번째에 '=' 처럼 가로 블럭을 두 개 쌓는 경우 와 i-1 번째에 ' | ' 처럼 세로 블럭 하나를 쌓는 경우를 합한 것이다.
반응형