목록11727번 (1)

철갑이의 이모저모

[백준] 11727번(2xn 타일링 2) with Python

문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 dp문제는 처음 풀어봐서 하나하나 그려서 규칙을 찾은 후 점화식을 구했다. 위의 그림과 같이 N이 3 이상 이면 N-1에서 2x1 타일이 붙고, N-2에서 1x2 타일 두 개, 2x2 타일이 한 개 붙는 규칙이 계속된다. 따라서, dp[n] = dp[n - 1] + dp[n - 2] * 2 dp[1]과 dp[2]를 미리 구해서 시작. 답 a = int(input()) dp = [0,1,3] for i in range(3, a + ..
알고리즘 2020. 10. 7. 23:25
이전 Prev 1 Next 다음